text:
# Cryptographic requirements for chaotic secure communications

## 1 Introduction

Modern telecommunications networks, and specially Internet and mobile telephones, have expanded the possibilities of user communications and information transmission to limits unimaginable a short time ago. There is a parallel growing demand of cryptographic techniques, which has originated an intense research activity and the search of new directions in cryptography. As a result, a rich variety of chaotic cryptosystems for end to end communications have been put forward , whose robustness and privacy are equally diverse.

There exist two main approaches to chaotic ciphers design: analog and digital. The first one is based on the concept of chaotic synchronization . In these systems, the information can be transmitted by the chaotic signal in a number of ways: chaotic masking , in which the analog message signal $`m(t)`$ is added to the output of the chaotic generator $`x(t)`$ in the transmitter; chaotic switching or chaos shift keying (CSK) , in which a binary message signal is used to choose between different chaotic attractors; chaotic modulation , in which a binary message modulates a parameter of the chaotic generator or when spread spectrum techniques are used to multiply the message signal by the chaotic one; and chaos control , in which small perturbations cause the symbolic dynamics of a chaotic system to track a prescribed symbol sequence. Regardless of the method used to transmit the message signal, the receiver has to synchronize with the transmitter’s chaotic generator to regenerate the chaotic signal $`x(t)`$ and thus recover the message $`m(t)`$.

The second approach to the design of chaos-based cryptosystems consists of using digital computers to iterate a chaotic map and mask the binary message in a number of ways . These ciphers do not depend on synchronization. Instead, they usually use one or more chaotic maps where the initial point $`x_0`$ and the parameter value $`\lambda `$ play the role of the key.

Most papers on this topic are published in physics and engineering journals and conferences, but not within the cryptography community. This explains why up to date little or no critical analysis has been made about the design process of these cryptosystems nor to the way the results are presented. Quoting Feng Bao : “The common annoying feature of the cryptosystems based on some mathematical models, e.g., those based on chaos systems, is that only the principle is given. They lack details, such as recommended key sizes and key generation steps, etc. Therefore it is not possible for others to implement the ciphers.”

We have detected that a systematic approach to the design and security evaluation is missing. To fill this void, in this paper we give some guidelines which should benefit new chaos-based cryptosystems. Following these guidelines, proposed cryptosystems would be presented in a more rigorous cryptographic way. Otherwise, they tend to be information concealment methods to frustrate the casual eavesdropper, but in no case the determined attacker and will not be taken seriously by cryptologists.

The paper is organized as follows. Sec. 2 lists requirements about the minimum practical details of the chaotic implementations that should be provided. In Sec. 3 the most important key related issues are discussed. In Sec. 4 the recommendations about how to make a security analysis are given. In Sec. 5 some basic but decisive considerations about the channel properties are offered. Sec. 6 concludes the paper.

## 2 The Implementation

For many chaotic systems, only basic concepts are described and implementation details are neglected. However, generally speaking, implementation details are important for cryptanalysts to judge whether or not there exist security defects. Also, it is obvious that the encryption speed and the implementation cost depend on such details. Therefore, the lack of implementation details makes it difficult to estimate the significance of the proposed cryptosystem, i.e. to analyze its security and overall performance.

### 2.1 The implementation of the chaotic systems

As we introduced in Sec. 1, there are two basic approaches to design chaotic ciphers: analog and digital. The first one is generally based on chaos synchronization, and the concerned chaotic systems are implemented in analog form. The second one is independent of chaos synchronization and the chaotic systems are completely implemented in digital computers. Additionally, in some conditions, the chaotic systems may be implemented in combined form, that is to say, both analog and digital parts are involved.

When analog parts are involved, the circuit diagrams to generate chaos should be given with enough details. When digital parts are involved, the following details should be given: the finite computing precision, the adopted digital arithmetic (fixed-point or floating-point), hardware/software configuration, etc. When both analog and digital parts are involved, details on A/D and D/A interfaces should also be described.

###### Rule 1

It should be thoroughly described how to implement the chaotic systems.

When the chaotic systems are (completely or partially) implemented in digital form, dynamical degradation will occur. This problem has been extensively studied in the last two decades, and it has been clarified that such dynamical degradation may cause security defects in chaos-based cryptosystems. To overcome this problem, some methods should be used to improve dynamical degradation of digital chaotic systems. A considerable countermeasure is to timely perturb the chaotic systems with a small pseudo-random signal. For more details, please refer to §2.5 of , in which Shujun Li gives a comprehensive review on this issue.

###### Rule 2

For chaotic systems implemented in digital form, the negative dynamical degradation should be taken into consideration.

### 2.2 The implementation of the cryptosystem

In the cryptography community, there are two well-known sayings: “it is quite easy to design a secure but very SLOW cipher”, and “it is quite easy to design a secure but very LARGE cipher”. If the security of a chaotic cryptosystem is reached with the loss of working efficiency, then its significance will be trivial and will not be accepted by pure cryptographers.

###### Rule 3

Without loss of security, the cryptosystem should be easy to implement with acceptable cost and should work with acceptable speed.

## 3 The key

A fundamental aspect of every cryptosystem is the key. An algorithm is as secure as its key. No matter how strong and well designed the algorithm might be, if the key is poorly chosen or the key space is small enough, the cryptosystem will be broken. Unfortunately, most chaotic secure communications schemes proposed to date fail to clearly, if at all, explain what the key is, how it should be chosen, and to thoroughly describe the available key space.

### 3.1 Key definition

A cryptosystem cannot exist without a key. Otherwise, it might be considered as a coding system, but never regarded as a secure system. In every cryptosystem an important effort must be devoted to clearly define and characterize the key. Many chaos-based secure communication systems proposed in the literature do not specify what the key is. It is assumed that the key must be made from the parameters of the chaotic system, but it is not clearly stated which parameters are, which their range is and what their precision or sensibility is.

###### Rule 4

What the key is should be thoroughly defined.

### 3.2 The key space

Once the key has been defined, it is equally important to characterize it, i.e., the key space must be studied in depth.

The size of the key space is the number of encryption/decryption key pairs that are available in the cipher system. The symbol $`v`$ is used to denote a key and the symbol $`𝐕`$ to denote a set of keys. Since the total number of possible keys is equal to $`r=|𝐕|`$, the set $`𝐕`$ or key space can be expressed as

$$𝐕=\{v_1,v_2,\mathrm{},v_r\}.$$
(1)
In classical cryptographic algorithms based on number theory, the key is usually a string of random bits generated by some automatic process. If the key is $`n`$ bits long, then every possible $`n`$-bit key must be equally likely, with probability $`2^n`$.

In most chaotic schemes, though, the key space is nonlinear because all the keys are not equally strong. We say that a key is *weak* or *degenerated* if it is easier to break a ciphertext encrypted with this key than breaking a ciphertext encrypted with another key. There exist keys giving rise to non-uniformly distributed chaotic values. As shown in Fig. 1, bifurcation diagrams help to discover the intervals for which a given parameter originates periodic orbits. These values should be avoided, and the chaotic bands should be preferred.

When many parameters are used simultaneously as part of the key, the mutual interdependence complicates the task of deciding which are the good intervals. In any case, the authors of the proposed cryptosystem should conduct a study of the chaotic regions of the parameter space from which valid keys, i.e., parameter values leading to chaotic behavior, can be chosen. Depending on the number of parameters chosen as part of the key, this region will have $`1,2,3,\mathrm{}`$ dimensions.

A possible way to describe the key space might be in terms of positive Lyapunov exponents. According to \[26, p. 196\], let $`𝐟`$ be a map of $`^m`$, $`m1`$, and $`\{𝐱_0,𝐱_1,𝐱_2,\mathrm{}\}`$ be a bounded orbit of $`𝐟`$. The orbit is chaotic if

1. it is not asymptotically periodic,
2. no Lyapunov exponent is exactly zero, and
3. the largest Lyapunov exponent is positive.

The largest Lyapunov exponent can be computed for different combinations of the parameters. If it is positive, then the combination can be used as a valid key. In Fig. 3, the chaotic region for the Henon attractor has been plotted following this criterion. This region corresponds to the keyspace. In general, parameters chosen from the lower white region give rise to periodic orbits, while parameters chosen from the upper white region give rise to unbounded orbits. Both regions should be avoided to get suitable keys. Only keys within the black region are good. And even within this region, there exist periodic windows, unsuitable for robust keys.

However, this type of irregular and often fractal chaotic region shared by most secure communication systems proposed is inadequate for cryptographic purposes because there is no easy way to define its boundary. Complete chaoticity for any parameter value should be preferred. A simple map which behaves in this way is the following skew tent map with a control parameter $`p(0,1)`$ (see also Fig. 2):

$$F(x)=\{\begin{array}{cc}x/p,\hfill & x[0,p]\hfill \\ (1x)/(1p),\hfill & x(p,1]\hfill \end{array}.$$
(2)
For any control parameter $`p(0,1)`$, the above piecewise linear map is always chaotic. In fact, for a piecewise linear chaotic map $`F:XX`$, if each linear segment is mapped onto $`X`$, the map will be chaotic and have many desired dynamical properties \[25, §3.2.1\]. Following such a result, as long as the control parameter does not change the mapping of each linear segment onto $`X`$, the obtained chaotic map will be good to construct chaotic cryptosystems.

###### Rule 5

The chaotic region which constitutes the key space $`𝐕`$ from which valid keys are to be chosen should be thoroughly specified.

It is sometimes taken for granted that the security of the encryption scheme is related to the size of the key space. A necessary, but not sufficient, condition for an encryption scheme to be secure is that the key space be large enough to frustrate brute force attacks (see Sec. 4.4). If the chaotic region does not meet this requirement, then it should be enlarged accordingly. However, the solution is not as simple as discretizing the region with a finer grain, because this could lead to *equivalent* keys, i.e., the same ciphertext is decrypted by two different keys. When two different keys are very close to each other, they could decrypt part or all the ciphertext. The safeguard between adjacent keys should be defined. In other words, the chaotic region should be discretized. In chaotic regime, the sensitivity to parameters will guarantee that two orbits starting from the same initial point but with slightly different parameters will diverge (the divergence rate is given by the Lyapunov exponents). However, the need for synchronization sometimes allows for an important parameter mismatch.

From a cryptographic point of view, the secret parameter should be sensitive enough to guarantee the so-called avalanche property: even when the smallest change occurs for the parameter, the ciphertext will change dramatically. Ideally, mathematical expectation of the change of ciphertext is half of the maximal value of all possible ciphertexts. For example, a natural idea to do so is to iterate the employed chaotic system for multiple times .

###### Rule 6

The useful chaotic region (the key space $`𝐕`$) should be discretized in such a way that the avalanche effect is guaranteed: two ciphertexts encrypted by two different keys $`v_1,v_2`$ chosen as close as possible from the key space $`𝐕`$ will be entirely different.

In some chaotic cryptosystems where more than one parameter is used as part of the key, it is possible to fix one of them and try to approximate the others. This is an undesirable behavior. Ideally, when the key is made from a number of parameters, the recovered signal after an illegal decryption attempt should never reveal that the attacker is approaching the exact key when one parameter is slowly varied. In other words, the recovered signal should appear the same if none of the parameters is guessed as if all but one of the parameters are guessed. This implies that the total key space is the product, and not the addition, of all the parameters involved.

###### Rule 7

Partial knowledge of the key should never imply partial knowledge of the cleartext.

### 3.3 Key generation

Once the key has been defined and the key space has been properly characterized, the process to choose good keys should be explained in detail. If some parameter ranges are given and the parameter values can be randomly chosen within these ranges, then it should be clear that there is no possibility of generating weak or degenerated keys.

Sometimes the useful chaotic region has irregular shapes. This shape could be enclosed in a regular one, such as a sphere or a cube, and the key could be chosen randomly within this regular shape and checked whether it is in the useful chaotic region.

###### Rule 8

The algorithm or process to generate valid keys from the key space $`𝐕`$ should be thoroughly specified.

## 4 Security analysis

When a new cryptosystem is proposed, it should always be accompanied by some security analysis. Although this analysis cannot comprise all the possible attacks against the newly created cipher, it should include at least the best known attacks and the corresponding results. This analysis helps to spot and correct flaws before the new scheme is published. That a cipher is resilient to all these attacks does not mean that it is secure, but at least it has undergone a certain amount of critical analysis. It is a necessary, but not sufficient, condition for security.

First of all, to resist common attacks, the designed cryptosystem should have the following basic cryptographic properties: confusion and diffusion. The first property reflects uniformity of all keys, and the second one reflects strong sensitivity (avalanche) of the key to small change. Obviously, Rule 6 mentioned above corresponds to diffusion. Here, we add a rule corresponding to confusion. To achieve confusion, statistical properties of the ciphertext, such as distribution, correlation and differential probabilities, should be independent of the exact value of the key. Many chaos-based cryptosystems are broken because of the lack of confusion property, such as E. Alvarez et al.’s cipher proposed in .

###### Rule 9

For different keys, no distinguishable difference of the ciphertext should be found from statistical point of view.

Next we describe the sort of attacks which should be accounted for.

### 4.1 Classical types of attacks

When cryptanalyzing an encryption algorithm, the general assumption made is that the cryptanalist knows exactly the design and working of the cryptosystem under study, i.e., he knows everything about the cryptosystem except the secret key. This is an evident requirement in today’s secure communications networks, usually referred to as Kerchoff’s principle \[28, p. 24\]. According to \[28, p. 25\], it is possible to differentiate between different levels of attacks on cryptosystems. They are enumerated as follows, ordered from the hardest type of attack to the easiest:

1. Cipher text only: The opponent possesses a string of cipher text, $`c`$.
2. Known plain text: The opponent possesses a string of plain text, $`p`$, and the corresponding cipher text, $`c`$.
3. Chosen plain text: The opponent has obtained temporary access to the encryption machinery. Hence he can choose a plain text string, $`p`$, and construct the corresponding cipher text string, $`c`$.
4. Chosen cipher text: The opponent has obtained temporary access to the decryption machinery. Hence he can choose a cipher text string, $`c`$, and construct the corresponding plain text string, $`p`$.

In each of these four attacks, the objective is to determine the key that was used. The last two attacks, which might seem unreasonable at first sight, are very common when the cryptographic algorithm, whose key is fixed by the manufacturer and unknown to the attacker, is embedded in a device which the attacker can freely manipulate. Daily life examples of such devices are electronic purse cards, GSM phone SIM (Subscriber Identity Module) cards, POST (Point Of Sale Terminals) machines, or web application session token encryption.

Many examples of how to break chaotic cryptosystems with known plaintext and chosen plaintext attacks can be found in .

###### Rule 10

At a minimum, it should be checked whether the cryptosystem is broken by simple known plaintext and chosen plaintext attacks.

### 4.2 Chaos-specific attacks

Many different methods have been proposed to attack chaotic encryption schemes, both for analog and digital systems. In this paper we will focus on the former. There are three possibilities for their cryptanalysis :

1. The extraction of the message signal $`m(t)`$ from the transmitted ciphertext signal $`c(t)`$.
2. The extraction of the chaotic masking signal $`x(t)`$.
3. The estimation of the parameters of the chaotic receiver, which are chosen from the key space $`𝐕`$.

The extraction of the message signal is generally possible if $`m(t)`$ is a periodic signal or consists of periodic frames with sufficient duration. It can be accomplished using different methods: spectral analysis techniques , autocorrelation and cross-correlation , filtering, or time series power estimation.

The chaotic masking signal $`x(t)`$ can be extracted using time delaying embedding reconstruction or return maps .

Parameter identification can be performed using generalized synchronization  or spectral analysis. Sometimes it is not even necessary to use approximate parameter values because transmitter and receiver are synchronized even under severe parameter mismatch .

###### Rule 11

At a minimum, it should be checked whether the cryptosystem is broken by well known chaos-specific attacks.

Also, as we mentioned above, when chaotic systems are implemented in digital form, the dynamical degradation can also cause security defects, which may bring weak keys and make brute force attacks easier. For examples with security defects caused by dynamical degradation of digital chaotic systems, please see  (or Chap. 4 of ).

### 4.3 Application-specific attacks

In some specific applications, there are some special attacks. For example, for digital images (videos), unlike normal one-dimensional data, strong correlation always exists between different pixels (transform coefficients). Such correlation information can be used to develop some correlation-based attacks, if the information is not successfully cancelled in cipher-images/cipher-videos.

In addition, in some applications cryptosystems should be specially optimized to make the encryption more efficient. However, sometimes there exists a tradeoff between efficiency and security, and the increment of efficiency causes decrement of security. For example, encrypting partial data of plain-videos is very useful to promote the encryption speed and make the cryptosystem practical, but it is possible to reconstruct partial visual information of plain-videos from partial non-encrypted data.

It is true that different uses of a same cipher in different applications may cause different levels of security .

###### Rule 12

At a minimum, it should be checked whether the cryptosystem is broken by well known application-specific attacks. If there exists a tradeoff between efficiency and security, explicit criteria should be given to show how to balance the two factors.

### 4.4 Brute force attacks

A brute force attack is the method of breaking a cipher by trying every possible key. The quicker the brute force attack, the weaker the cipher. Feasibility of brute force attacks depends on the key space size $`r`$ of the cipher and on the amount of computational power available to the attacker. Given today’s computer speed, it is generally agreed that a key space of size $`r<2^{100}`$ is insecure.

###### Rule 13

To prevent brute force attacks, the key space size should be $`r>2^{100}`$.

However, this requirement might be very difficult to meet by some proposed ciphers because the key space does not allow for such a big number of different strong keys. For instance, Fig. 3 was created using a resolution of $`10^3`$, i.e., there are $`1400\times 3000`$ different points. To get a number of keys $`r>2^{100}10^{30}`$, the resolution should be $`10^{15}`$. However, with that resolution, thousands of keys would be equivalent, unless there is a strong sensitivity to parameter mismatch, which is usually lost by synchronization.

## 5 The channel

Many secure communications systems proposed are tested in Matlab or some other simulation program, but not under real conditions. It should be noted that a real channel is subjected to noise, has a limited bandwith, and is attenuated. When designing a new secure communications scheme, besides security considerations, the channel characteristics should be taken into account, thus preventing the system from failing when tested in a noisy, bandwith-limited, and attenuated channel.

###### Rule 14

The secure communications system should work in a channel with $`30`$ dB signal/noise ratio, with limited bandwith, and with an attenuation between $`3`$ dB and $`+1`$ dB.

## 6 Conclusions

We have presented a set of guidelines which are recommended to be adopted by every secure communications systems designer. These guidelines do not constrain the freedom and creativity of the designer, but, if followed, guarantee a reasonable degree of security and cryptographic rigor. In this way, new chaos-based cryptosystems will be easier considered by the cryptography community, and both worlds will be benefited.

## Acknowledgements

This research was supported by Ministerio de Ciencia y Tecnología, Proyecto TIC2001-0586.


format: text

text:
# Untitled Document

This article has been replaced by gr-qc/0412011


text:
# A solution to the tennis ball problem

## 1 Introduction

The statement of the tennis ball problem is the following. There are $`2n`$ balls numbered $`1,2,3,\mathrm{},2n`$. In the first turn balls 1 and 2 are put into a basket and one of them is removed. In the second turn balls 3 and 4 are put into the basket and one of the three remaining balls is removed. Next balls 5 and 6 go in and one of the four remaining balls is removed. The game is played $`n`$ turns and at the end there are exactly $`n`$ balls outside the basket. The question is how many different sets of balls may we have at the end outside the basket.

It is easy to reformulate the problem in terms of lattice paths in the plane that use steps $`E=(1,0)`$ and $`N=(0,1)`$. It amounts to counting the number of lattice paths from $`(0,0)`$ to $`(n,n)`$ that never go above the path $`NE\mathrm{}NE=(NE)^n`$. Indeed, if $`\pi =\pi _1\pi _2\mathrm{}\pi _{2n1}\pi _{2n}`$ is such a path, a moment’s thought shows that we can identify the indices $`i`$ such that $`\pi _{2ni+1}`$ is a $`N`$ step with the labels of balls that end up outside the basket. The number of such paths is well-known to be a Catalan number, and this is the answer obtained in .

The problem can be generalized as follows . We are given positive integers $`t<s`$ and $`sn`$ labelled balls. In the first turn balls $`1,\mathrm{},s`$ go into the basket and $`t`$ of them are removed. In the second turn balls $`s+1,\mathrm{},2s`$ go into the basket and $`t`$ among the remaining ones are removed. After $`n`$ turns, $`tn`$ balls lie outside the basket, and again the question is how many different sets of balls may we have at the end. Letting $`k=t,l=st`$, the problem is seen as before to be equivalent to counting the number of lattice paths from $`(0,0)`$ to $`(ln,kn)`$ that use $`N`$ and $`E`$ steps and never go above the path $`N^kE^l\mathrm{}N^kE^l=(N^kE^l)^n`$. This is the version of the problem we solve in this paper.

From now on we concentrate on lattice paths that use $`N`$ and $`E`$ steps. To our knowledge, the only cases solved so far are $`k=1`$ and $`k=l=2`$. The case $`k=1`$ is straightforward, the answer being a generalized Catalan number $`\frac{1}{(l1)n+1}\left(\genfrac{}{}{0pt}{}{ln}{n}\right)`$. The case $`k=l=2`$ (corresponding to the original problem when $`s=4,t=2`$) is solved in  using recurrence equations; here we include a direct solution. This case is illustrated in Fig. 1, to which we refer next. A path $`\pi `$ not above $`(N^2E^2)^n`$ is “almost” a Catalan path, in the sense that it can raise above the dashed diagonal line only through the dotted points. But clearly between two consecutive dotted points hit by $`\pi `$ we must have an $`E`$ step, followed by a Catalan path of odd semilength, followed by a $`N`$ step. Thus, $`\pi `$ is essentially a sequence of Catalan paths of odd semilength. If $`G(z)=_n\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)z^n`$ is the generating function for the Catalan numbers, take the odd part $`G_o(z)=(G(z)G(z))/2`$. Then expand $`1/(1zG_o(z))`$ to obtain the sequence $`1,6,53,554,6363,\mathrm{}`$, which agrees with the results in .

Let $`P`$ be a lattice path from $`(0,0)`$ to $`(m,r)`$, and let $`b(P)`$ be the number of paths from $`(0,0)`$ to $`(m,r)`$ that never go above $`P`$. If $`PN`$ denotes the path obtained from $`P`$ by adding a $`N`$ step at the end of $`P`$, then clearly $`b(P)=b(PN)`$. However, it is not possible to express $`b(PE)`$ simply in terms of $`b(P)`$, where $`PE`$ has the obvious meaning. As is often the case in counting problems, one has to enrich the objects under enumeration with additional parameters that allow suitable recursive decompositions. This is precisely what is done here: equations (2) and (3) in the next section contain variables $`x`$ and $`y`$, corresponding to two parameters that we define on lattice paths not above a given path $`P`$. These equations are the key to our solution.

The basis of our approach is the connection between lattice paths and matroids established in , where the link with the tennis ball problem was already remarked. For completeness, we recall the basic facts needed from  in the next section. In Section 3 we present our solution to the tennis ball problem, in the form of explicit expressions for the corresponding generating functions; see Theorem 1. In Section 4 we show how the same method can be applied to a more general problem. We conclude with some remarks.

## 2 Preliminaries

The contents of this section are taken mainly from , where the reader can find additional background and references on matroids, Tutte polynomials and lattice path enumeration.

A *matroid* is a pair $`(E,)`$ consisting of a finite set $`E`$ and a nonempty collection $``$ of subsets of $`E`$, called *bases* of the matroid, that satisfy the following conditions: (1) No set in $``$ properly contains another set in $``$, and (2) for each pair of distinct sets $`B,B^{}`$ in $``$ and for each element $`xBB^{}`$, there is an element $`yB^{}B`$ such that $`(Bx)y`$ is in $``$.

Let $`P`$ be a lattice path from $`(0,0)`$ to $`(m,r)`$. Associated to $`P`$ there is a matroid $`M[P]`$ on the set $`\{1,2,\mathrm{},m+r\}`$ whose bases are in one-to-one correspondence with the paths from $`(0,0)`$ to $`(m,r)`$ that never go above $`P`$. Given such a path $`\pi =\pi _1\pi _2\mathrm{}\pi _{m+r}`$, the basis corresponding to $`\pi `$ consists of the indices $`i`$ such that $`\pi _i`$ is a $`N`$ step. Hence, counting bases of $`M[P]`$ is the same as counting lattice paths that never go above $`P`$.

For any matroid $`M`$ there is a two-variable polynomial with non-negative integer coefficients, the Tutte polynomial $`t(M;x,y)`$. It was introduced by Tutte  and presently plays an important role in combinatorics and related areas (see ). The key property in this context is that $`t(M;1,1)`$ equals the number of bases of $`M`$.

Given a path $`P`$ as above, there is a direct combinatorial interpretation of the coefficients of $`t(M[P];x,y)`$. For a path $`\pi `$ not above $`P`$, let $`i(\pi )`$ be the number of $`N`$ steps that $`\pi `$ has in common with $`P`$, and let $`e(\pi )`$ be the number of $`E`$ steps of $`\pi `$ before the first $`N`$ step, which is 0 if $`\pi `$ starts with a $`N`$ step. See Fig. 1 for an illustration.

Then we have (see \[1, Th. 5.4\])

$$t(M[P];x,y)=\underset{\pi }{}x^{i(\pi )}y^{e(\pi )},$$
(1)
where the sum is over all paths $`\pi `$ not above $`P`$. A direct consequence is that $`t(M[P];1,1)`$ is the number of such paths.

Furthermore, for the matroids $`M[P]`$ there is a rule for computing the Tutte polynomial that we use repeatedly (see \[1, Section 6\]). If $`PN`$ and $`PE`$ denote the paths obtained from $`P`$ by adding a $`N`$ step and an $`E`$ step at the end of $`P`$, respectively, then

$`t(M[PN];x,y)`$ $`=`$ $`xt(M[P],x,y),`$ (2)
$`t(M[PE];x,y)`$ $`=`$ $`{\displaystyle \frac{x}{x1}}t(M[P],x,y)+\left(y{\displaystyle \frac{x}{x1}}\right)t(M[P];1,y).`$ (3)
The right-hand side of (3) is actually a polynomial, since $`x1`$ divides $`t(M[P];x,y)t(M[P];1,y)`$. The key observation here is that we cannot simply set $`x=y=1`$ in (3) to obtain an equation linking $`t(M[PE];1,1)`$ and $`t(M[P];1,1)`$.

For those familiar with matroid theory, we remark that $`M[PN]`$ and $`M[PE]`$ are obtained from $`M[P]`$, respectively, by adding an isthmus and taking a free extension; it is known that formulas (2) and (3) correspond precisely to the effect these two operations have on the Tutte polynomial of an arbitrary matroid.

From (1) and the definition of $`i(\pi )`$ and $`e(\pi )`$, equation (2) is clear, since any path associated to $`M[PN]`$ has to use the last $`N`$ step. For completeness, we include a direct proof of equation (3).

We first rewrite the right-hand side of (3) as

$`{\displaystyle \frac{x}{x1}}(t(M[P];x,y)t(M[P];1,y))+yt(M[P];1,y)=`$
$`{\displaystyle \underset{\pi }{}}{\displaystyle \frac{x}{x1}}y^{e(\pi )}(x^{i(\pi )}1)+y^{e(\pi )+1}=`$
$`{\displaystyle \underset{\pi }{}}y^{e(\pi )}(y+x+x^2+\mathrm{}+x^{i(\pi )}),`$
where the sums are taken over all paths $`\pi `$ that do not go above $`P`$.

To prove the formula, for each path $`\pi `$ not above $`P`$ we find $`i(\pi )+1`$ paths not above $`PE`$ such that their contribution to $`t(M[PE];x,y)`$ is $`y^{e(\pi )}(y+x+x^2+\mathrm{}+x^{i(\pi )})`$. Consider first the path $`\pi _0=E\pi `$; it clearly does not go above $`PE`$ and its contribution to the Tutte polynomial is $`y^{e(\pi )+1}`$. Now for each $`j`$ with $`1ji(\pi )`$, define the path $`\pi _j`$ as the path obtained from $`\pi `$ by inserting an $`E`$ step after the $`j`$th $`N`$ step that $`\pi `$ has in common with $`P`$ (see Fig. 2). The path $`\pi _j`$ has exactly $`j`$ $`N`$ steps in common with $`PE`$, and begins with $`e(\pi )`$ $`E`$ steps.

It remains only to show that each contribution to the Tutte polynomial of $`M[PE]`$ arises as described above. Let $`\pi ^{}`$ be a path that never goes above $`PE`$ and consider the last $`N`$ step that $`\pi ^{}`$ has in common with $`PE`$; clearly the next step must be $`E`$. Let $`\stackrel{~}{\pi }`$ be the path obtained after removing this $`E`$ step. Since $`\pi ^{}`$ had no $`N`$ steps in common with $`PE`$ after the $`E`$ step removed, the path $`\stackrel{~}{\pi }`$ does not go above $`P`$. Thus the path $`\pi ^{}`$ can be obtained from $`\stackrel{~}{\pi }`$ by adding an $`E`$ step after the $`i(\pi ^{})`$-th $`N`$ step that $`\stackrel{~}{\pi }`$ has in common with $`P`$, and hence $`\pi ^{}`$ arises from $`\stackrel{~}{\pi }`$ as in the previous paragraph. It is easy to show that $`\pi ^{}`$ cannot be obtained in any other way by applying the procedure described above, and this finishes the proof.

## 3 Main result

Let $`k,l`$ be fixed positive integers, and let $`P_n=(N^kE^l)^n`$. Our goal is to count the number of lattice paths from $`(0,0)`$ to $`(ln,kn)`$ that never go above $`P_n`$. From the considerations in the previous section, this is the same as computing $`t(M[P_n];1,1)`$. Let

$$A_n=A_n(x,y)=t(M[P_n];x,y).$$

By convention, $`P_0`$ is the empty path and $`A_0=1`$.

In order to simplify the notation we introduce the following operator $`\mathrm{\Phi }`$ on two-variable polynomials:

$$\mathrm{\Phi }A(x,y)=\frac{x}{x1}A(x,y)+\left(y\frac{x}{x1}\right)A(1,y).$$

Then, by equations (2) and (3) we have

$$A_{n+1}=\mathrm{\Phi }^l(x^kA_n),$$

where $`\mathrm{\Phi }^i`$ denotes the operator $`\mathrm{\Phi }`$ applied $`i`$ times.

For each $`n0`$ and $`i=1,\mathrm{},l`$, we define polynomials $`B_{i,n}(x,y)`$ and $`C_{i,n}(y)`$ as

$`B_{i,n}`$ $`=`$ $`\mathrm{\Phi }^i\left(x^kA_n(x,y)\right),`$
$`C_{i,n}`$ $`=`$ $`B_{i,n}(1,y).`$
We also set $`C_{0,n}(y)=A_n(1,y)`$. Notice that $`B_{l,n}=A_{n+1}`$, and $`C_{0,n}(1)=A_n(1,1)`$ is the quantity we wish to compute.

Then, by the definition of $`\mathrm{\Phi }`$, we have:

$$\begin{array}{cccc}B_{1,n}\hfill & =\hfill & \frac{x}{x1}x^kA_n\hfill & +\left(y\frac{x}{x1}\right)C_{0,n};\hfill \\ B_{2,n}\hfill & =\hfill & \frac{x}{x1}B_{1,n}\hfill & +\left(y\frac{x}{x1}\right)C_{1,n};\hfill \\ & \mathrm{}\hfill & & \\ B_{l,n}\hfill & =\hfill & \frac{x}{x1}B_{l1,n}\hfill & +\left(y\frac{x}{x1}\right)C_{l1,n};\hfill \\ A_{n+1}\hfill & =\hfill & B_{l,n}.\hfill & \end{array}$$

In order to solve these equations, we introduce the following generating functions in the variable $`z`$ (but recall the coefficients are polynomials in $`x`$ and $`y`$):

$$A=\underset{n0}{}A_nz^n,C_i=\underset{n0}{}C_{i,n}z^n,i=0,\mathrm{},l.$$

We start from the last equation $`A_{n+1}=B_{l,n}`$ and substitute repeatedly the value of $`B_{i,n}`$ from the previous equation. Taking into account that $`_nA_{n+1}z^n=(A1)/z`$, a simple computation yields

$$\frac{A1}{z}=\frac{x^{k+l}}{(x1)^l}A+(yxyx)\underset{i=1}{\overset{l}{}}\frac{x^{i1}}{(x1)^i}C_{li}.$$

We now set $`y=1`$ and obtain

$$A\left((x1)^lzx^{k+l}\right)=(x1)^lz\underset{i=1}{\overset{l}{}}x^{i1}(x1)^{li}C_{li},$$
(4)
where it is understood that from now on we have set $`y=1`$ in the series $`A`$ and $`C_i`$.

By Puiseux’s theorem (see \[5, Chap. 6\]), the algebraic equation in $`w`$

$$(w1)^lzw^{k+l}=0$$
(5)
has $`k+l`$ solutions in the field $`^{\mathrm{fra}}((z))=\{_{nn_0}a_nz^{n/N}\}`$ of fractional Laurent series. Proposition 6.1.8 in  tells us that exactly $`l`$ of them are fractional power series (without negative powers of $`z`$); let them be $`w_1(z),\mathrm{},w_l(z)`$.

We substitute $`x=w_j`$ in (4) for $`j=1,\mathrm{},l`$, so that the left-hand side vanishes, and obtain a system of $`l`$ linear equations in $`C_0,C_1,\mathrm{},C_{l1}`$, whose coefficients are expressions in the $`w_j`$, namely

$$\underset{i=1}{\overset{l}{}}w_j^{i1}(w_j1)^{li}zC_{li}=(w_j1)^l,j=1,\mathrm{},l.$$
(6)
Notice that, since the $`C_i`$ are (ordinary) power series, the solutions $`w`$ of (5) that we substitute in (4) cannot have negative powers of $`z`$, hence they must be $`w_1,\mathrm{},w_l`$. We remark the similarity of this technique with the one devised by Tutte for counting rooted planar maps (see, for instance, ).

It remains only to solve (6) to obtain the desired series $`C_0=_nA_n(1,1)z^n`$. The system (6) can we written as

$$\underset{i=0}{\overset{l1}{}}\left(\frac{w_j}{w_j1}\right)^izC_{li1}=w_j1,j=1,\mathrm{},l.$$

The left-hand sides of the previous equations can be viewed as the result of evaluating the polynomial $`_{i=0}^{l1}(zC_{li1})X^i`$ of degree $`l1`$ at $`X=w_j/(w_j1)`$, for $`j`$ with $`1jl`$. Using Lagrange’s interpolation formulas, we get that the coefficient of $`X^{l1}`$ in this polynomial is

$$zC_0=\underset{j=1}{\overset{l}{}}\frac{w_j1}{_{ij}\left(\frac{w_j}{w_j1}\frac{w_i}{w_i1}\right)}.$$

By straightforward manipulation this last expression is equal to

$$\underset{j=1}{\overset{l}{}}(1w_j)\underset{j=1}{\overset{l}{}}\frac{(w_j1)^{l1}}{_{ij}(w_jw_i)}=\underset{j=1}{\overset{l}{}}(1w_j),$$

where the last equality follows from an identity on symmetric functions (set $`r=0`$ in Exercise 7.4 in ).

Thus we have proved the following result.

###### Theorem 1.

Let $`k,l`$ be positive integers. Let $`q_n`$ be the number of lattice paths from $`(0,0)`$ to $`(ln,kn)`$ that never go above the path $`(N^kE^l)^n`$, and let $`w_1,\mathrm{},w_l`$ be the unique solutions of the equation

$$(w1)^lzw^{k+l}=0$$

that are fractional power series. Then the generating function $`Q(z)=_{n0}q_nz^n`$ is given by

$$Q(z)=\frac{1}{z}(1w_1)\mathrm{}(1w_l).$$

Remark that, by symmetry, the number of paths not above $`(N^lE^k)^n`$ must be the same as in Theorem 1, although the algebraic functions involved in the solution are roots of a different equation.

In the particular case $`k=l`$ the solution can be expressed directly in terms of the generating function $`G(z)=_n\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)z^n`$ for the Catalan numbers, which satisfies the quadratic equation $`G(z)=1+zG(z)^2`$. Indeed, (5) can be rewritten as

$$w=1+z^{1/k}w^2,$$

whose (fractional) power series solutions are $`G(\zeta ^jz^{1/k})`$, $`j=0,\mathrm{},k1`$, where $`\zeta `$ is a primitive $`k`$-th root of unity. For instance, for $`k=l=3`$ (corresponding to $`s=6,t=3`$ in the original problem), $`\zeta =\mathrm{exp}(2\pi i/3)`$ and we obtain the solution

$`{\displaystyle \frac{1}{z}}(1G(z^{1/3}))(1G(\zeta z^{1/3}))(1G(\zeta ^2z^{1/3}))=`$
$`1+20z+662z^2+26780z^3+1205961z^4+58050204z^5+\mathrm{}.`$
In the same way, if $`l`$ divides $`k`$ and we set $`p=(k+l)/l`$, the solution can be expressed in terms of the generating function $`_n\frac{1}{(p1)n+1}\left(\genfrac{}{}{0pt}{}{pn}{n}\right)z^n`$ for generalized Catalan numbers; the details are left to the reader. As an example, for $`k=4`$, $`l=2`$, we obtain the series

$`{\displaystyle \frac{1}{z}}(1H(z^{1/2}))(1H(z^{1/2}))=`$
$`1+15z+360z^2+10463z^3+337269z^4+11599668z^5+\mathrm{},`$
where $`H(z)=_n\frac{1}{2n+1}\left(\genfrac{}{}{0pt}{}{3n}{n}\right)`$ satisfies $`H(z)=1+zH(z)^3`$.

## 4 A further generalization

In this section we solve a further generalization of the tennis ball problem. Given fixed positive integers $`s_1,t_1,\mathrm{},s_r,t_r`$ with $`t_i<s_i`$ for all $`i`$, let $`s=s_i,t=t_i`$. There are $`sn`$ labelled balls. In the first turn we do the following: balls $`1,\mathrm{},s_1`$ go into the basket and $`t_1`$ of them are removed; then balls $`s_1+1,\mathrm{},s_1+s_2`$ go into the basket and among the remaining ones $`t_2`$ are removed; this goes on until we introduce balls $`ss_r+1,\mathrm{},s`$, and remove $`t_r`$ balls. After $`n`$ turns there are $`tn`$ balls outside the basket and the question is again how many different sets of $`tn`$ balls may we have at the end.

The equivalent path counting problem is: given $`k_1,l_1,\mathrm{},k_r,l_r`$ positive integers with $`k=k_i`$, $`l=l_i`$, count the number of lattice paths from $`(0,0)`$ to $`(ln,kn)`$ that never go above the path $`P_n=(N^{k_1}E^{l_1}\mathrm{}N^{k_r}E^{l_r})^n`$. The solution parallels the one presented in Section 3. We keep the notations and let $`A_n=t(M[P_n];x,y)`$, so that

$$A_{n+1}=\mathrm{\Phi }^{l_r}(x^{k_r}\mathrm{}\mathrm{\Phi }^{l_1}(x^{k_1}A_n)\mathrm{}).$$

As before, we introduce $`l`$ polynomials $`B_{i,n}(x,y)`$ and $`C_{i,n}(y)=B_{i,n}(1,y)`$, but the definition here is a bit more involved:

$$\begin{array}{ccc}B_{i,n}\hfill & =\mathrm{\Phi }^i(x^{k_1}A_n),\hfill & i=1,\mathrm{},l_1;\hfill \\ B_{l_1+i,n}\hfill & =\mathrm{\Phi }^i(x^{k_2}B_{l_1,n}),\hfill & i=1,\mathrm{},l_2;\hfill \\ B_{l_1+l_2+i,n}\hfill & =\mathrm{\Phi }^i(x^{k_3}B_{l_1+l_2,n}),\hfill & i=1,\mathrm{},l_3;\hfill \\ & \mathrm{}\hfill & \\ B_{ll_r+i,n}\hfill & =\mathrm{\Phi }^i(x^{k_r}B_{ll_r,n}),\hfill & i=1,\mathrm{},l_r.\hfill \end{array}$$
(7)
We also set $`C_{0,n}(y)=A_n(1,y)`$. Again, from the definition of $`\mathrm{\Phi }`$, we obtain a set of equations involving $`A_n`$, $`A_{n+1}=B_{l,n}`$, the $`B_{i,n}`$ and $`C_{i,n}`$. We define generating functions $`A`$ and $`C_i`$ ($`i=0,\mathrm{},l`$) as in Section 3.

Starting with $`A_{n+1}=B_{l,n}`$, we substitute repeatedly the values of the $`B_{i,n}`$ from previous equations and set $`y=1`$. After a simple computation we arrive at

$$A\left((x1)^lzx^{k+l}\right)=(x1)^l+zU(x,C_0,\mathrm{},C_{l1}),$$
(8)
where $`U`$ is a polynomial in the variables $`x,C_0,\mathrm{},C_{l1}`$. Observe that the difference between (8) and equation (4) is that now $`U`$ is not a concrete expression but a certain polynomial that depends on the particular values of the $`k_i`$ and $`l_i`$.

Let $`w_1,\mathrm{},w_l`$ be again the power series solutions of (5). Substituting $`x=w_j`$ in (8) for $`j=1,\mathrm{},l`$, we obtain a system of linear equations in the $`C_i`$. Since the coefficients are rational functions in the $`w_j`$, the solution consists also of rational functions; they are necessarily symmetric since the $`w_j`$, being conjugate roots of the same algebraic equation, are indistinguishable.

Thus we have proved the following result.

###### Theorem 2.

Let $`k_1,l_1,\mathrm{},k_r,l_r`$ be positive integers, and let $`k=k_i`$, $`l=l_i`$. Let $`q_n`$ be the number of lattice paths from $`(0,0)`$ to $`(ln,kn)`$ that never go above the path $`(N^{k_1}E^{l_1}\mathrm{}N^{k_r}E^{l_r})^n`$, and let $`w_1,\mathrm{},w_l`$ be the unique solutions of the equation

$$(w1)^lzw^{k+l}=0$$

that are fractional power series. Then the generating function $`Q(z)=_{n0}q_nz^n`$ is given by

$$Q(z)=\frac{1}{z}R(w_1,\mathrm{},w_l),$$

where $`R`$ is a computable symmetric rational function of $`w_1,\mathrm{},w_l`$.

As an example, let $`r=2`$ and $`(k_1,l_1,k_2,l_2)=(2,2,1,1)`$, so that $`k=l=3`$. Solving the corresponding linear system we obtain

$$R=\frac{(1w_1)(1w_2)(1w_3)}{2w_1w_2w_3(w_1w_2+w_1w_3+w_2w_3)},$$

and

$$Q(z)=\frac{1}{z}R=1+16z+503z^2+19904z^3+885500z^4+42298944z^5+\mathrm{}.$$

It should be clear that for any values of the $`k_i`$ and $`l_i`$ the rational function $`R`$ can be computed effectively. In fact, a simple computer program could be written that on input $`k_1,l_1,\mathrm{},k_r,l_r`$, outputs $`R`$.

## 5 Concluding Remarks

It is possible to obtain an expression for the generating function of the full Tutte polynomials $`A_n(x,y)`$ defined in Section 3. We have to find the values of $`C_0,C_1,\mathrm{},C_{l1}`$ satisfying the system (6) and substitute back into (4). After some algebraic manipulation, the final expression becomes

$$\underset{n0}{}A_n(x,y)z^n=\frac{(xw_1)\mathrm{}(xw_l)}{(zx^{k+l}(x1)^l)(yw_1(y1))\mathrm{}(yw_l(y1))}.$$

Taking $`x=y=1`$ we recover the formula stated in Theorem 1.

On the other hand, references  and  also study a different question on the tennis ball problem, namely to compute the sum of the labels of the balls outside the basket for all possible configurations. For a given lattice path $`P_n`$, this amounts to computing the sum of all elements in all bases of the matroid $`M[P_n]`$. We remark that this quantity does not appear to be computable from the corresponding Tutte polynomials alone.

Finally, as already mentioned, the technique of forcing an expression to vanish by substituting algebraic functions was introduced by Tutte in his landmark papers on the enumeration of planar maps. Thus the present paper draws in more than one way on the work of the late William Tutte.