Complex distributions emerging in filtering and compression
G. J. Baxter R. A. da Costa S. N. Dorogovtsev J. F. F. Mendes






Departamento de Física da Universidade de Aveiro & I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal



Departamento de Física da Universidade de Aveiro & I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal



Departamento de Física da Universidade de Aveiro & I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal
A.F. Ioffe Physico-Technical Institute, 194021 St. Petersburg, Russia


Departamento de Física da Universidade de Aveiro & I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal
School of Computer and Communication Sciences and School of Life Sciences, École Polytechnique Fédéral de Lausanne, 1015 Lausanne EPFL, Switzerland




In filtering, each output is produced by a certain number of different inputs. We explore the 
statistics of this degeneracy in an explicitly treatable filtering problem in which filtering performs the maximal compression of relevant information contained in inputs (arrays of zeroes and ones). 
This problem serves as a reference model for the statistics of filtering and related sampling problems. 
The filter patterns in this problem conveniently allow a microscopic, combinatorial consideration. This allows us to find the statistics of outputs, namely the exact distribution of output degeneracies, for 
arbitrary input sizes. We observe that the resulting degeneracy distribution of outputs decays as e^-clog^αd with degeneracy d, where c is a constant and exponent α>1, i.e. faster than a power law. 

Importantly, its form 
essentially depends on the size of the input data set, appearing to be closer to a power-law dependence for small data set sizes than for large ones. We demonstrate that for sufficiently small input data set sizes 
typical for empirical studies, this distribution could be easily perceived as a power law. 

We extend our results to filter patterns of various sizes and demonstrate that the shortest filter pattern provides the maximum informative representations of the inputs.




Complex distributions emerging in filtering and compression  

    J. F. F. Mendes
    December 30, 2023
==============================================================












§ INTRODUCTION

 

Compression, filtering, and cryptography are related areas in signal and information processing 
<cit.>.
By definition, a large number of possible inputs are mapped to a smaller number of possible outputs, so that a given output may correspond to multiple inputs, which number is the output's degeneracy.
A similar problem emerges in cooperative systems with a large number of local minima in the energy landscape, in particular, in spin glasses and deep learning neural networks <cit.>. 
The configuration space of a system of this sort can be divided into a set of domains (basins) of attraction of these minima. 
One can ask: what is the statistics of these domains of attraction, what is the distribution of their sizes? This is analogous to the degeneracy statistics problem.
These statistics are important because the degeneracy distribution gives the most relevant entropy when studying information problems <cit.>, that is, it is the distribution containing the most information relevant to the system under study. 

These issues were explored in a recent series of works <cit.> which exploited the principle of maximum entropy,  
see also Refs. <cit.>. 

The finding of Refs. <cit.> is that 
maximally informative samples drawn from data exhibit statistics with broad distributions. 

More specifically, their entropy optimization based theory predicts power-law like distributions of degeneracy of maximally informative outputs (minimal sufficient representations). The title of the paper “Minimum description codes are critical” <cit.> published in the journal Entropy highlights the message of that theory in the most succinct way. 
On the other hand, distributions markedly distinct from power laws can be observed in empirical distributions for this kind of problem, for example, a collection of empirical curves in Fig. 1 of Ref. <cit.>. 









One obstacle to understanding such phenomena is that the need to obtain sufficient samples to resolve the degeneracy distribution limits the system size which can be examined. In the present work we contribute to these efforts by proposing a model for which sampling distributions can be obtained exactly, for the entire state space and up to large system sizes.

 We introduce and explore a reference filtering problem straightforwardly treatable through purely combinatorial techniques.
 This filter 
 extracts all positions of a given local pattern in the input, see Fig. <ref>.

We study a family of such filter patterns and demonstrate that the smallest pattern, extracting single ones from the inputs, generates outputs with the highest entropy of the degeneracy distribution, called relevance, Fig. <ref> and Table <ref>. 

According to Refs. <cit.>, this type of information entropy is maximized by the representations of the samples of a complex system which provide the most information, the maximally informative representations,  which occurs in a critical region where the sample distribution becomes complex. Outside of this region outputs are either nearly all the same, or nearly all different, giving no useful information about the underlying system. Note that the entropy of the samples themselves, called the resolution, is not maximum in this critical region, but in the limit that all samples are different.

We establish 



a link between filtering and sampling problems based on the idea that filter patterns of different lengths with their positions can serve as sampling variables. We demonstrate that the behavior of our filtering problem is analogous to that found in the more complex systems of Refs. <cit.>. The entropy of the degeneracy distribution of filter outputs increases as the filter length decreases, but vanishes in the extreme limit, for which resolution is maximised, with outputs being identical to inputs. Thus within a family of filters, the most informative filter is the shortest one with length greater than one.


We directly obtain the complex degeneracy distributions for outputs generated from various input sets. We develop efficient recursive methods that allow us to find this distribution for large input strings, as can be seen in Fig.<ref>, which would not be accessible through empirical sampling methods.
Due to the tractability of this problem, we are able to identify precisely how these distributions deviate from a power-law dependence. We find scaling forms that accurately describe the tail of the degeneracy distributions (see Fig. <ref>).  
We discover that these distributions are essentially shaped by the size of the input data. That is, input data sets of relatively small size, typical for empirical studies, produce degeneracy distributions of outputs that are closer to a power law than the distributions of outputs from very large input data sets. 
Finally, we develop a mean field theory and obtain the asymptotics of the degeneracy distribution and the spectrum of degeneracies.  

Our findings indicate that the phenomena we observe should apply to more general filtering and compression problems.

Our paper is organized in the following way. In Sec. <ref> we introduce our filter and the synthetic input data sets for it. 
In Sec. <ref> we describe how the filtering problem can be viewed as sampling of a complex system.
In Secs. <ref>, <ref>, and <ref> we obtain the basic relations for the degeneracy of outputs, develop our algorithm, obtain the complex degeneracy distributions of outputs for the complete input data sets, and describe their features. We develop the mean-field theory of these distributions in filtering in Sec. <ref>. In Sec. <ref> we obtain the degeneracy distributions of outputs for uniformly random input data sets of various sizes. In Sec. <ref> we discuss our results and indicate possible generalizations.
In the Appendix we 


give the combinatorial derivations of recursive relations used in Sec. <ref> and explicit asymptotics. 
The exact results obtained by our algorithm and recursions are provided in the Supplementary Material <cit.>. 










§ A REFERENCE FILTERING PROBLEM

 

We study the distribution of outputs in a solvable filtering problem by implementing a purely combinatorial, microscopic approach not involving entropy considerations. 
Let the input data be a set of N strings of zeroes
 and ones 
(x_i), x_i=0,1,  of length n, 
 assuming the periodic condition x_1=x_n+1. 
We consider two types of data set. The first set is the complete set of all possible unique inputs. Its size N is determined by the size n of inputs, N = 2^n.
Second, we consider data sets of arbitrary size N consisting of strings of uniformly randomly generated zeroes 
 and ones 
 constrained by the same periodic condition as above.
 In the latter situation, some of the elements of a data set may coincide. Clearly, in the limit N→∞, we arrive at a situation equivalent to the complete data set. (We stress that the random data set of size N=2^n differs from the the complete data set.) 

The filter works as follows: every instance of a specific pattern in the input is marked by a one in the corresponding position in the output. All other positions are marked with zeroes. This produces a minimal coding of the positions of the pattern occurrences in the input.
We illustrate the results from a few example filter patterns in Fig. <ref>. We observe complex degeneracy distributions reminiscent of those observed in, for example, Ref. <cit.>.









For the sake of simplicity, in the remainder of this paper we focus on the simplest of these filters.
Each sequence of ones of length 1 in the input (i.e., every 1 whose neighbors are both zeroes)
 gives 1 at the same position in the output. All other sequences of ones 
 or zeroes in the input produce zeroes in the corresponding places in the output, as shown in Fig. <ref>. In other words, the input vector (x_i), i=1,2,...,n, x_i=0,1, is transformed to the output vector with the following components: 


    y_i = (1-x_i-1)x_i(1-x_i+1) 
    .


As we will see, this filter is the maximally informative one, in a family of similar filters.
Other filter patterns may be analysed using the same methods we describe below.














§ FILTERING AS A SAMPLING PROBLEM



Let us discuss the link between filtering and sampling in more detail. 
The input x_i to our filtering problem is a string of n ones and zeroes. It contains alternating contiguous chains of ones and zeroes of different lengths, so that one may completely define the sequence by listing the starting positions of all the strings of ones and their respective lengths.
With this in mind, one may reformulate the problem of filtering for patterns in sequences as sampling 
a system of correlated discrete variables in the following way.

Let us introduce the set of discrete variables {s_i^l}, for i=1,...,n and l=1,...,n-1. The (`spin') variable s_i^l is 1 if the input has a string of l ones beginning at position i, and is 0 otherwise.
These variables correspond to the outputs of filters for chains of consecutive ones.
We include one more variable which distinguishes between the states of all zeroes and all ones.
The system, then, has 2^m, m=n(n-1)+1, possible states.


Strings of ones in the input do not overlap with each other, which restricts the configurations of the variables {s_i^l} that can occur. We include these constraints in our system by imposing a cost for each violation of the mutual exclusion rules, the cost function being 


    U(s⃗) = 
    
    ∑_s_i^l,s_j^m s_i^l s_j^m [
    
      Θ(i+l,j) + Θ(j+m,i)
      ]
    ,


where 

    Θ(a,b)
         = 
    
    1     a  n ≥ b, 
    
    0

functions as a cyclic Heaviside function.

We now have a complex system consisting of m state variables, whose interactions are governed by the cost function U.
Each of the 2^n possible input sequences corresponds to a different minima of this cost function.


Now let us consider the sampling of this system. Suppose we may 

measure only n of these variables s_i^l. Which n variables will be most informative about the state of the system?
intuitively, shorter filter patterns, i.e. smaller values of l, should provide more detailed information about the system, and indeed the variables s_i^l=1 contain the most information about the state of the system. 





(To see this, note that the variable s_i^l gives information about the state of l+2 input digits. In particular, when s_i^l=1, it fully determines l+2 digits of the input, which happens for a fraction 2^-(l+2) of the inputs.
Thus, the total amount of information conveyed by s_i^l in terms of the number of digits of the input it reveals is (l+2)2^-(l+2), which is indeed maximum for l=1.)





The set {s_i^1} is also the most informative representation of the input from the perspective of Ref. <cit.>, in the sense that samples obtained from observing these n variables have a larger entropy of their degeneracy distributions, Eq. (<ref>), than samples using any other subset of n variables. 
This is apparent from the fact that any subset of n variables containing larger filters will have less available configurations, see also Table <ref>. We detail this analogous behavior further in Sec. <ref>.














§ OUTPUTS AND THEIR DEGENERACIES FOR COMPLETE INPUT DATASET

 









Let us begin by considering the complete input data set, all 2^n 
different configurations of zeroes and ones. 
Each output consists of isolated ones separated by strings of zeroes of various lengths. The total number of possible outputs, M(n), is then the number of ways of arranging isolated ones in a chain of length n.
This number coincides with the number of different configurations of dimers in a closed chain (ring) of length n: 


    M(n) = n ∑_k=0^[n/2]1/n - kn - k  k
    ,


where [n/2] is the integer part of n/2, see Appendix <ref>. 

Comparing this number for successive values of n, we see that 
M (n) = M (n - 1) + M(n - 2), with initial conditions M (3) = 4, M (4) = 7.
The elements of the sequence may be written in terms of the roots of the characteristic equation <cit.>

    z^2 - z = 1 
    .

Thus


    M(n) = (1 + √(5)/2)^n + (1 - √(5)/2)^n ≅(1 + √(5)/2)^n =z_g^n 
    ,


where the last expression gives the large n limit. 
Here the largest root (1 + √(5))/2 = 1.61803... ≡ z_g 
is the famous golden ratio. 



The key point for our study is that the degeneracy of an output is the product of the degeneracies of the strings of zeroes 
 between ones in the output. 
 As is clear from Eq. (<ref>), the presence of a 1 in an output at position i fixes the digits of its inputs at positions i-1, i, and i+1. These digits must be 0, 1, and 0, respectively. This is true for each 1 in the output.
On the other hand, each of the remaining digits of these inputs compatible with a given output must be either a 0 or be a 1 with one or two neighboring ones.  
All the degrees of freedom in the input corresponding to a given output 
correspond to these digits. 

Let an output with m≥ 1 ones contain m strings of zeroes with lengths ℓ_1,ℓ_2,...,ℓ_m. Then the degeneracy of this output equals 


    d = ∏_i=1^md̃(ℓ_i) 
    .


Here d̃(ℓ) is the number of input strings of length ℓ, having the first and last digits 0, that  generate an output string of ℓ zeroes. 
This number plays an important role in our problem, similar to prime numbers in number theory, so we call the d̃(ℓ) prime degeneracies. 


Suppose that the output contains μ_ℓ strings of zeroes of length ℓ, ℓ=1,2,..., where  


    m + ∑_ℓ≥1ℓμ_ℓ = n
    .


Then Eq. (<ref>) may be rewritten 


    d = ∏_ℓ≥ 1 [d̃(ℓ)]^ μ_ℓ


for m≥1.

Let us find the prime degeneracies explicitly. 
The number of these configurations, i.e., the degeneracy d̃(ℓ) of the output string of ℓ zeroes, 
can be obtained recursively by taking into account three points: 

(i) Relevant input configurations of length ℓ are obtained by inserting 

0 or 

1 into each relevant configuration of length ℓ-1 between the first and second positions of the sequence. (Recall that the first and last positions of the input sequence are fixed to 0.) 

(ii) Input strings of length ℓ beginning and/or ending with 010 are irrelevant, and so they should be removed from the set generated at the previous step.  
These configurations can be obtained by inserting two digits 10 into each relevant input string of length ℓ-2 between its first and second positions.

(iii) Finally, there exist input strings, compatible with the output string of ℓ zeroes, 
that cannot be obtained by inserting a single digit into relevant input strings of length ℓ-1 between their first and second positions. These are the input strings of length ℓ beginning with 0110. These inputs can be obtained by inserting 110 into each relevant input string of length ℓ-3 between their first and second positions.

Following these rules, the degeneracy of a string of ℓ zeroes at the output, prime degeneracy d̃(ℓ), can be written recursively as a linear difference equation: 


    d̃(ℓ) = 2 d̃(ℓ-1) - d̃(ℓ-2) + d̃(ℓ-3)
 

with the initial condition d̃(1)=d̃(2)=d̃(3)=1. 

The solution of Eq. (<ref>) may be explicitly expressed in terms of the complex roots z_1, z_2, and z_3 of the characteristic equation 


    z^3=2z^2-z+1
    ,
 

giving 


    d̃(ℓ) = C_1 z_1^ℓ + C_2 z_2^ℓ  + C_3 z_3^ℓ
      ,


 where 
 

    C_1   =   (z_1 - 1)/[(z_1 - z_2)(z_1 - z_3)],
    
    
    C_2   =   (z_2 - 1)/[(z_2 - z_1)(z_2 - z_3)],
    
    
    C_3   =   (z_3 - 1)/[(z_3 - z_1)(z_3 - z_2)]
    .


One of the roots of Eq. (<ref>), z_1, say, is real, 


    z_1≡ z_d =1.75488...  
    .
 

It determines the large ℓ asymptotics of the prime degeneracies d̃(ℓ):  


    d̃(ℓ) ≅z_d/z_d^4-2 z_d^ℓ
 

where we used the identity C_1 = z_d/(z_d^4-2). The two other roots are complex conjugate numbers, 


    z_2,3 = 0.122561... ± 0.744862... i
    .
 


The special case of the periodic output of length n with all digits 0 has to be considered separately. 
First let us take an arbitrary digit of the input. The number of input configurations where this digit is 0 and the resulting output has only zeroes 
 is given by d̃(n+1), because the fixed 0 of the periodic input plays the role of first and last digit of the configurations of a string of n+1 digits. 
If the chosen digit is 1, then the number of the relevant input configurations equals 1+∑_i=2^n-1 i d̃(n-i), where the sum over i accounts for the configurations where the digit is in a group of i consecutive ones, 
plus one configuration with all input digits equal to 1.
Consequently, we obtain the following expression for the degeneracy of the output with all zeroes: 


    d_D(n) = 1 + d̃(n+1) + ∑_i=2^n-1 i d̃(n-i)
    ,


which is the largest possible degeneracy of an output of a given length. Applying the recursion relation for prime degeneracies d̃, Eq. (<ref>) 
 to the terms on the right-hand side of Eq. (<ref>) 
we find that the largest degeneracy d_D(n) satisfies the same difference equation as Eq. (<ref>) 
though with different initial condition, see, e.g., Ref. <cit.> and the On-line Encyclopedia of Integer Sequencies <cit.>. We present this equation here for future reference, 


    d_D(n) = 2 d_D(n-1) - d_D(n-2) + d_D(n-3)
 

with the initial condition  d_D(3)=5, d_D(4)=10, and d_D(5)=17. 
With these initial condition, we get the explicit solution of this equation, 


    d_D(n) = z_1^ℓ + z_2^ℓ  + z_3^ℓ
    ,


where z_1≡ z_d,z_2,z_3 are given by Eqs. (<ref>) and (<ref>), and its large n asymptotics 


    d_D(n) ≅ z_d^n
    .
















§ CALCULATING THE EXACT DEGENERACY SPECTRUM

 









In principle, for each of the 2^n possible inputs
 we can obtain, one by one, an output numerically by applying Eq. (<ref>). 
In practice, we use a more efficient algorithm described below. 
This algorithm focuses on outputs with a fixed number of ones
 and exploits the factorization of the output degeneracies, see Eq. (<ref>).  
 
The full list of degeneracies can be found from integer partitions in an explicit form, as follows.

Let us introduce the operator P, which generates all integer partitions of positive integer k into r integers, that is, P(k,r) is the matrix whose rows i=1,2,...,w are all different integer partitions { P_i1(k,r), P_i2(k,r),..., P_ij(k,r),..., P_ir(k,r)} of k into r integers, ∑_j=1^r  P_ij(k,r)=k <cit.>. 

For an output of length n, we consider all partitions of n-m into m integers, for all possible m=1,2,...,[n/2]. 
For each such partition, [i.e., a row of P(n-m,m)],
we find the degeneracy 
d_i = ∏_j d̃( P_ij(n-m,m)) [see Eq. (<ref>)]. Some of them coincide, so we find the union of them. 
Finally, we add the largest degeneracy d_D(n) (corresponded to m=0) to the resulting set. In summary, for the full set of degeneracies D_full(n), we have


    D_full(n) =  d_D(n) ⋃ {⋃_m=1^[n/2][ ⋃_i=1^w 
    ∏_j=1^md̃( P_ij(n-m,m)) ] }


with d̃(ℓ) and d_D(n) provided by Eqs. (<ref>) and (<ref>), respectively. 

For each integer partition, i.e., for each row i of the matrix P(n-m,m) we introduce a function giving the number 
of pieces of length ℓ present in this partition,

    μ_ℓ^(i)(n-m,m) ≡∑_j=1^m δ(ℓ, P_ij(n-m,m)),

so that


    n-m    =   ∑_ℓℓμ_ℓ^(i)(n-m,m)
    ,
    
    
    m    =   ∑_ℓμ_ℓ^(i)(n-m,m) 
    .


One can then write 


    d_i = ∏_j d̃( P_ij(n-m,m)) = ∏_ℓ [d̃(ℓ)]^μ_ℓ^(i)(n-m,m)
    .


The number of outputs that contain m chains of zeros with lengths specified by the integer partition P_i(n-m,m) is then obtained by
considering the number of distinct permutations of the m strings of zeros, multiplying by n, and finally dividing by m, giving



    N[  P_i(n-m,m)] = 
    n(m-1)!/∏_ℓμ_ℓ^(i)(n-m,m)!,


where the product in the denominator is over the lengths of the parts of this partition. 
The total number of outputs with degeneracy d is then finally:  



    N(d,n) =  δ[d,d_D(n)] 
    
          
    + ∑_m=1^[n/2]∑_i=1^w n(m-1)!/∏_ℓμ_ℓ^(i)(n-m,m)! δ[d,∏_ℓ [d̃(ℓ)]^μ_ℓ^(i)(n-m,m)]
    ,


where δ(a,b) is the Kronecker symbol. 
This is the expression we use for computing N(d,n) in an efficient way. 
For the sake of brevity, hereafter we refer to N(d,n) as a degeneracy distribution, without 
normalization. 

The distribution N(d,n) can also be built up recursively starting from small values of d and n, as we show in Appendix <ref>. 













§ OUTPUT DEGENERACY DISTRIBUTION FOR COMPLETE INPUT DATASETS

 

Using this algorithm we obtained  the number of outputs N(d) for the full spectrum of degeneracies d for n up to 120, see Supplementary Material <cit.>.
These results demonstrate that the degeneracies d_i , i=1,...,D, form a discrete spectrum of values where D is the rank of the largest degeneracy, and d_1=1. 

Fig. <ref> shows the resulting distribution and the corresponding cumulative distribution N_cum(d) for n=21, 50, and 120. 
Here N_cum(d_i) ≡∑_j=i^D  N(d_j). In particular, N_cum(d_1)=M(n), i.e., the total number of outputs. 
Figs. <ref>(b), (c), and (d) 
demonstrate that the cumulative degeneracy distributions decay with d more rapidly than a power law.  
On the other hand, the decay of the cumulative distribution is well described by the function


    N_cum(d) ∝ e^-cln^α d = d^-cln^α-1 d
    ,


where c is a positive number and exponent α 
approaches 2.3 as n→∞, see the inset in Fig. <ref> (b). 

Notice that the degeneracy distribution for smaller n, Fig. <ref> (a), appears more like a power law than the degeneracy distribution for larger n, Fig. <ref>(c), for example, since the range of d increases with n, while the exponent cln^α-1 d of the function 
d^-cln^α-1 d varies slowly. 
Similarly, the cumulative distribution plotted in log-log scale for n=21 deviates from linear (power-law behavior) noticeably less than for larger n. 

The wide range of degeneracies d that we observe enable us to present 
Fig. <ref> (b) showing ln{-ln[ N_cum(d)/ N_cum(1)]}  vs. lnln d.  
This plot supports the functional form given in Eq. (<ref>). Note that in Fig. <ref> we assumed that the coefficient factor of the asymptotics in Eq. (<ref>) is close to N_cum(1), which is justified by the results. 
Fig. <ref> shows how the set of degeneracies 
D_full(n) varies with n, see below for more detail. 

In Sec. <ref> we derived the explicit expression for the largest degeneracy d_D(n) corresponding to the output with all zeroes, 
Eq. (<ref>), and found its large n asymptotics, d_D(n) ≅ z_d^n, Eq. (<ref>). As is natural, N(d_D,n)=1. 
The second largest degeneracy corresponds to an output with a single 1. The third largest degeneracy is for an output with two ones separated by a single 0. The fourth largest degeneracy is of the output with two ones separated by three 0s. Clearly, N(d_D-1,n)= N(d_D-2,n)= N(d_D-3,n)=n. Using the asymptotics of d̃(ℓ), Eq. (<ref>), we
find that, asymptotically, at large n, 


    d_D-1(n) ≅z_d^n/7.48391... = z_d^n/z_d^4 - 2 
    ,
    
          
    d_D-2(n) ≅z_d^n-2/z_d^4 - 2
    ,
    
          
    d_D-3(n) ≅z_d^n-3/z_d^4 - 2
    .



One may also notice a complex structure in the cumulative distributions
Figs. <ref>(b), (d), and (f), N_cum(d) resembling a staircase, with steep jumps between steps.
The heights of these jumps are especially large in the region of high degeneracies. 

Similar structures may be observed in real systems, see for example Fig. 3 of Ref. <cit.>.

Inserting the asymptotics of d̃(ℓ), Eq. (<ref>), into the expression for the degeneracy, Eq. (<ref>), we see that outputs with the same number of ones have degeneracies exponentially close to z_d^n/(z_d^4 - 2)^2 if these ones are separated by many zeroes  and n is large. 
The slight deviations from this asymptotic value mean that the degeneracies are split among many points falling in a narrow range.
For example, in the rightmost step, corresponding to outputs with exactly two ones, 
the number of these outputs is approximately n^2/2 because there are relatively few outputs in which the two ones are close together. 
This is the height of this jump.

These degeneracies are split into a set of about n/2 distinct values, 
corresponding to different intervals between the ones.
each one occurs in n outputs corresponding to the location of the same structure in different parts of the ring. Other jumps are produced by outputs with m strongly separated ones, 
or by outputs with, e.g., a pair of ones separated by one 0 with m-2 ones
  far from each other and from that pair, and so on. 
  This forms  the rich staircase-like structure that we observe in Figs. <ref>(b), (d), and (e) 
  and that is also reflected in Fig. <ref>.  

  Note that any short filter of our sort
  
  will produce a similar complex structure in the degeneracy distribution, as the degeneracy associated to a chain of zeroes (in output) of a given length must asymptotically grow exponentially with the length of the chain, as in Eq. (<ref>). 

We list the key numbers defining the asymptotics of a few example cases in Table <ref>, including an example of a two dimensional input, and give the full degeneracy distributions for selected cases in Fig. <ref>. 

It is worth discussing the meaning of these results, and their interpretation in terms of sampling of complex systems.
In particular let us consider the results for the family of filters composed of a string of ones with a zero at each end, 010, 0110, 01110, etc., indicated in boldface in the Table. We can consider the length of these filters as a crude control parameter of our sampling. Intuitively, we expect shorter filters to be more informative. 

Resolution, defined as the entropy of a sample:

    H[y] 
    = -1/N∑_i=1^Nlog(d_i/N).
    = -∑_d d N(d,n)/Nlog(d/N)

is a measure of the ability to distinguish, at the output, between different input states.
If the sample contains M distinct outputs, all with the same degeneracy, the resolution is simply ln M, see Eq. (29).
Notice that this is the case when all outputs are different (all degeneracies equal to 1, M=N), and also when all outputs are the same (degeneracy equal to N, M=1).
The inverse of the probability of a particular output gives the expected number of distinct outputs, if we assume the probabilities to be uniform.
In this sense, we can regard the resolution as the expectation of the logarithm of the number of distinct states in a sample, based on the observation of one random state.

Shorter filter patterns correspond to higher resolution. 
The resolution attains its maximum value for the filter pattern 0 or 1, either of which results in a unique output for each input 
(in the case of 1,  the output is identical to the input).
However in this case all outputs are distinct, and so these filters are

not informative about the system being sampled.
As shown in <cit.>, the measure which indicates the informativeness of a sample, is the entropy of the degeneracy distribution,


    H[d] = -∑_d d N(d,n)/Nlog(d N(d,n)/N),
 

where N= 2^n for the complete input set.
This is called the relevance.
Comparing Eqs. (29) and (30) shows that the resolution is never smaller than the relevance, H[y] ≥ H[d]. 

As can be seen in the Table, the relevance is greater for shorter filters, but is actually zero for the shortest possible filters 0 and 1. (In this extreme, z_d = 1, while z_g = z_a = 2.) We measured the relevance for a variety of short filter patterns. Specifically, we find that the entropy H[d] is maximal for the filter pattern extracting single ones, on which we focus in this work, and so

this pattern provides the most informative representations of the inputs



The number z_d gives the asymptotics of the largest degeneracies. It quickly approaches 2 as the filter pattern length increases. The largest degeneracies ≅ z_d^n. Since N = 2^n, this means that almost all outputs concentrate in a few outputs, and in the limit, in a single state, i.e. all outputs 
are the same 
and the filter patterns are not informative. For the shortest few patterns, the value of z_d quickly falls, accompanied by a rapidly increasing relevance, indicating a transition to informative sampling.
On the contrary, z_g, which gives the total number of outputs M(n), increases with decreasing filter length, as shorter filters have more possible outputs. 






 Taken together, these results indicate that the maximally informative sampling for a given family of filters is the shortest pattern having length greater than 1. This behavior is analogous to the transition observed in more complex problems (see for example <cit.>), reinforcing the relevance of our tractable model to the study of more complex problems.







Importantly, the sets of outputs obtained with the larger filters are subsets of the set of the outputs obtained with our reference filter pattern 010. For this pattern, the value z_g, which gives the asymptotics of the number of different outputs, is maximal, and the number of different outputs is the largest one. (Notice that the zero-pattern in Table <ref> has the same z_g as the reference pattern but a lower entropy H[d].) 
Some filters have the property that two occurrences of the pattern cannot partially overlap. All such filter patterns of a given length give an identical degeneracy distribution, as we show in the table. We suggest that the filtering problem with such non-overlapping filter patterns of an arbitrary finite length can be solved in a way similar to our reference pattern. 
















In Appendix <ref> we derive the chain of linear coupled recursion relations 
for the number of outputs of degeneracy d, N(d,n), see Eqs. (<ref>) and (<ref>). 
These recursions generate exact N(d,n) for finite d and n, and in this sense provide the exact full spectrum of degeneracies. (There recursions also provide us with the explicit leading large n asymptotics of N(d,n), Eq. (<ref>), for an arbitrary d.)
In particular, Eq. (<ref>) with the initial conditions, Eq. (<ref>), provides N(1,n) which is the number of configurations having only groups of zeroes of length 1, 2, and 3 between single ones. 
We find the large n asymptotics for this number:  


    N(1,n) ≅ z_a^n
    ,


where 


    z_a =1.46557...


is the real root of the characteristic equation z^4 = z^2 + z + 1.

Note that there are three key constants in this problem, z_g, z_d, and z_a, which appear in the main asymptotics: 
M(n) ≅ z_g^n, d_D(n) ≅ z_d^n, and N(1,n) ≅ z_a^n. 
Indeed, z_g enters the distribution N(d,n)/M(n) after normalization, z_d enters the asymptotics for degeneracies, see, e.g., Eq. (<ref>) for d̃(ℓ) and (<ref>) for d_i(n), and z_a enters the asymptotics for N(d,n), Eqs. (<ref>) and (<ref>). 
In fact, all moments of N(d,n) exponentially diverge with n, ∑_i=1^D d_i^k  N(d_i,n) ≅ c_k^n, where the numbers c_k and their large k asymptotics are presented in Appendix <ref>. Clearly, for the first moment we have ∑_i=1^D d_i  N(d_i,n) = 2^n.

Using Eq. (<ref>) we obtain the full set of degeneracies
D_full(n) for different n, shown in Fig. <ref>, and the series of total number of discrete values of degeneracy D(n) versus input size, represented in Fig. <ref>, see also the Supplementary Material <cit.>.
 As is natural, D(n) is smaller than the number p(n) of integer partitions of n. Fig. <ref> demonstrates that D(n) is close to p(n)/n for large n. The well known large n asymptotics p(n) ≅1/4√(3)n  e^π√(2n/3) <cit.> enables us to estimate D(n)∼ e^π√(2n/3). 

By ranking the full set of degeneracies D_full(n) for n=120 we arrive at Fig. <ref>, where the main plot presents the number of different degeneracies lower than or equal to d vs. d, increasing roughly as exp[π√(2ln d/3ln z_d)] in the region 1 ≪ d ≪ d_D, and the inset shows the number of different degeneracies higher than or equal d vs. d. The latter demonstrates a staircase-like structure similar to that of N_cum(d).

In Fig. <ref> we also plot the number of different degeneracies lower than or equal to d in the infinite system, i.e., the rank of each degeneracy d. To obtain the full set of different degeneracies for n→∞ up to some d_max we generate the set of prime degeneracies d̃≤ d_max. We start by listing all powers m≥ 1 of the first prime degeneracy d̃ while d̃^m≤ d_max. Then, we multiply each member of that list by increasing powers of the next prime degeneracy, while the product stays lower or equal to d_max, and so on with all the remaining prime degeneracies d̃≤ d_max.
This procedure will result in duplicate degeneracies that should be removed, particularly for those values of d that have non-unique multiplicative partitions in terms of the prime degeneracies. 

For example, the two smallest (larger than 1) prime degeneracies are d̃(4) = 2 and d̃(5) = 4, so a multiplicative partition of d with at least a part equal to d̃(5) = 4 is not unique because there is at least another partition of d where the contribution of the 4 for given in terms of d̃(4) as 2^2.
However, apart from the partitions with parts equal to 4, the non-unique partitions are very rare, see Appendix <ref>.
In fact d̃(4) = 2 is the only prime degeneracy d̃(ℓ) that can be expressed as a product of lower d̃ for all ℓ≤ 5000. 

The rank of the degeneracies in the infinite system can be estimated with precision for large d, as shown by the black line 
in Fig. <ref>.
For large ℓ the logarithms of prime degeneracies are uniformly distributed lnd̃(ℓ) ≈ℓln z_d. 
Assuming that all degeneracies d have a unique factorization in terms of the prime degeneracies d̃,
the expected number of different degeneracies smaller than d ∼ z_d^m would be rank  d ≈∑_n ≤ m p(n), where p(n) is the number of integer partitions of n.
The vast majority of the degeneracies for which the assumption does not hold are the values of d which are multiples of 4, because that factor 4 can also be expressed as 2^2.
We therefore remove from each term of the previous sum the number of integer partitions that have at least one factor equal to 2, which is given by p(n-2), and write for large d:


    rank  d  ≈∑_n ≤ln d / ln z_d [ p(n) - p(n-2) ] 
    
          ≈ p(ln d / ln z_d) + p( ln d / ln z_d-1) 
    
          ≈exp( π√(2/3)√(ln d /ln z_d))/π 2 √(3) (ln d /ln z_d) [1 -(13 π/72+1/π)√(3  ln z_d / 2 ln d )],


where we have used the two leading terms of the asymptotic expansion of the number of integer partitions <cit.>


    p(n) ≈exp( π√(2/3)√(n))/4 √(3) n [1 -(π/72+1/π)√(3/ 2 n)].


Fig. <ref> demonstrates that rank  d as a function of d is well described by the estimate Eq. (<ref>).




























§ MEAN-FIELD THEORY

  

Here we develop a mean-field theory enabling us to describe 
the cumulative distribution of degeneracies, N_cum(d), in the region of large d where there are few ones 
 in the outputs, and so the gaps of zeroes 
 between them are typically large. In this situation one can assume that the  ones 
 exist in a sea (or a mean field) of zeroes,  
far from each other, so that the degeneracy of an output is completely determined by the number of its ones 
 (and the output size n). 

This ansatz is based on the observation that the three terms on the right-hand side of Eq. (<ref>) behave very differently for increasing ℓ:
The first term grows exponentially as z_d^ℓ, where z_d≡ z_1=1.754877... is real.
The combined contribution of the other two terms is also real, since z_2=z_3^* (here ^* denotes the complex conjugate). It decays exponentially because | z_2 | = | z_3 | = 0.754877...<1.
Thus, for increasing ℓ, the deviation of the asymptotics  


    d̃(ℓ) ≅ C_1 z_d^ℓ


from the exact value of d̃(ℓ) approaches 0 exponentially rapidly, making this approximation 
excellent for large ℓ.

Consider an output with m ones,
separated by m strings of zeroes 
 of length ℓ_1, ℓ_2, ..., ℓ_k. 
If all ℓ_i ≫ 1 the degeneracy d(m) of this output with m ones 
 is accurately given by the asymptotic expression 


    d(m) = ∏_i=1^m C_1 z_d^ℓ_i =  C_1^m  z_d^n-m
    ,


where we used the 
condition ∑_i=1^m ℓ_i = n-m that 
the number of ones plus the number of zeroes must be equal to the total number of digits n. 

The total number of different outputs with m ones is


    N(m) 
    = n/n-mn-mm
    ,


see Eq. (<ref>) in Appendix <ref>. 
Notice that N(m) 
coincides with the m-th term of the sum in Eq. (<ref>), as it must.

One should stress that although we derived the 
expressions for d(m) 
and N(m) 
for m>0, these expressions are equally valid in the special case of m=0. 
Indeed, Eq. (<ref>) gives N(0)=1, which is exact. 
Further, Eq. (<ref>) gives d(0)≅ z_d^n for large n coinciding with d_D≅z_d^n, Eq. (<ref>). 
Thus Eqs. (<ref>) and (<ref>) 
work very well also for m=0. 

For m=1 we find a similar situation in terms of accuracy. In this case there is a single string of zeroes 
 of size n-1, then every output with a single 1 has degeneracy equal to d̃(n-1).
The deviation between d(1)= C_1 z_1^n-1 
and d̃(n-1) decays exponentially with n:

For each value of m>1 there is actually more than one possible value for the degeneracy, that depends on the particular distribution of lengths of the strings of zeroes. 
Nonetheless, for large n and m ≪ n most of the outputs contain only large strings of zeroes.
Therefore the set of points (d,  N_cum) for k=0,1,2,... describes the exact cumulative distribution N_cum(d)  well at the points d=d(m) in the region of large d, which corresponds to m≪ n. There are jumps in the cumulative distribution at these points when n is large, and N_cum(m) approaches the top points of these jumps. 

The resulting mean-field theory expression for the distribution takes the following form:


    N(d,n)     =    δ(d,d_D(n)) 
    
    
        +    ∑_m=1^[n/2]n/n-mn-mm δ(d,z_d^n/(z_d^4-2)^m)
    .


This approximation is compared with the exact cumulative distribution in Fig. <ref>.
The approximation can also be obtained from the exact result for N(d,n), Eq. (<ref>), by approximating the weighted sum ∑_i of Kronecker symbols in the expression for N(d,n) by a single Kronecker symbol with a factor. 
One may also obtain the asymptotics of this distribution, as shown in Appendix <ref>.











§ DEGENERACY DISTRIBUTIONS OF OUTPUTS FOR RANDOMLY GENERATED INPUT DATASETS

  









We observed in the previous section that the outputs generated by complete input data sets do not produce real power laws. 
One should note, however, that in empirical studies, input data sets, typically, are not complete. Usually, when inputs (input size n) are sufficiently large, the input data set sizes, N, are much smaller than of complete data sets, N ≪ C^n, C>1. Based on the sets of outputs of complete data sets, which we obtained in the previous section (listed in the Supplementary Material <cit.>), here we find and explore the distribution of outputs of randomly generated data sets of various sizes. (In principle, these sizes can also be bigger than or equal to that of complete data sets.)

Let the size of a randomly generated input data set be N, i.e., we apply filtering to N randomly generated rings of n zeroes and ones. 
We assume that all degeneracies of the outputs of the corresponding complete input data set are known, namely the full set of pairs { d_i,  N(d_i) }, where i=1,2,...,D, D is the total number of degeneracies for this n in the case of a complete input data set. Then for the randomly generated input data set we obtain the following expected number of outputs of degeneracy d: 


    ⟨ N⟩(d) = N  d∑_i=1^D N(d_i) (d_i/2^n)^d(1-d_i/2^n)^N-d
    .


The probability that a randomly generated input string produces a given output is simply d_i/2^n, where d_i is the degeneracy of the output with respect to the total input set. The probability that d of the N inputs produce this output is then simply given by a binomial expression. Summing over all total degeneracies (multiplying by the number of instances of a given degeneracy d_i and summing over i) gives the above expression.

Here outputs of any degeneracy within the interval 1 ≤ d ≤ d_D are present with nonzero probability, in contrast to the case of the complete input data set. The results of the application of this formula coincide with those obtained by recording statistics of outputs directly filtered from randomly generated inputs. 

Let us apply Eq. (<ref>), for instance, to the cases n=21 [see Fig. <ref>(a) above for the complete input data set consisting of all 2^21 configurations] and n=120, 
and inspect the distributions of outputs of uniformly randomly generated input sets of different sizes.
The results are shown in Fig. <ref>.
For each size of the random input data set we present the degeneracy distribution and its cumulative counterpart. 
Interestingly, the form of these distributions is remeniscent of samples from real systems, see for example Fig. 5 of Ref. <cit.>.
These figures demonstrate that for N≪ 2^n, the distributions indeed resemble a power law. 
The reason is that for sufficiently small N, the distribution does not approach the large values 
of d for which the variation of the exponent cln^α-1 d in N_cum(d) ∝ d^-cln^α-1 d, 
[see Eq. (<ref>)], becomes noticeable.
As N approaches 2^n, the distributions become closer to their counterparts for the complete input data set. Clearly, the distributions obtained in the limit N→∞ will coincide with those found for the complete input data set.

Curiously, one may obtain distributions with a very similar form for different values of n by choosing N in order to maintain the scaling variable

    s = (z_d/2)^n N

constant.
 For example, compare the first with the third row and the second with the fourth in Fig. <ref>. 
This combination follows from the fact that the binomial product in Eq. (<ref>), as a function of d, forms a narrow peak centered at d_i N/2^n, which produces (z_d/2)^n N for the largest degeneracy d_D ≅ z_d^n.  
This scaling disappears in the region of small degeneracies. 
Note that for small N,

 Eq. (<ref>) gives ⟨ N⟩(1) ≈ N, since ∑_i d_i  N(d_i)≅2^n.
 In fact this is true as long as

N≪ (4/c_2)^n, where ∑_i d_i^2  N(d_i)=c_2^n with c_2=3.139...,  see Appendix <ref>. 

Thus 
the vast 
majority of outputs have degeneracy 1 in this situation. 












§ DISCUSSIONS AND CONCLUSIONS

  

Our straightforward, purely combinatorial treatment reveals features of distributions of outputs hidden from other approaches.  
For complete input data sets passed through our filter, we have obtained degeneracy distributions markedly distinct from power laws. On the other hand, these distributions decay as N_cum(d) ∝ e^-cln^αd, α>1, much slower than exponentially, and in this sense they can still be called “critical”. We have observed that the entire form of these output distributions essentially depends on the input size n, which strongly differs, for example, from heavy tailed degree distributions of complex networks having exponential cutoffs <cit.>.

For randomly generated input data sets, we found degeneracy distributions which could easily be taken for power laws in empirical studies, if the data set size N is essentially smaller than 2^n. As N→∞, these distributions approach the clearly non power-law shape of the distributions for the complete input data set. 
Thus we show that the size of an input data set matters for these problems. 

Our model filter can be used as a convenient reference filtering problem. 
Although apparently rather different in construction, we argue that our problem can serve as a tractable representative model for sampling of complex systems.
We focused on simple input sets which were uniformly random strings of zeroes 
 and ones. 
Correlated inputs 
are more challenging for analytical treatment. Exploring the simplest filter patterns, we showed that the statistics of outputs is determined not by the form of filter patterns but rather by what occurs in the gaps of zeroes
 between them. 

The degeneracy corresponding to each such gap can be found using recursion relationships.
We then used an integer partitions apparatus to aggregate the statistics of prime degeneracies from these gaps, finding the exact full spectrum of output degeneracies.

Considering the permutations of the integer partitions allows us to calculate the resulting exact degeneracy distribution N(d,n). Alternatively, using multiplicative partitions we derive coupled linear recursions providing the exact N(d,n) for any finite d and n and the explicit large n asymptotics.
Finally we developed a mean-field theory which describes the approximate degeneracy spectrum, degeneracy distribution and their asymptotic behavior. Our mean-field theory of Sec. <ref> also derives from the gaps between outputs.

These results show that in filter problems of this kind, the statistics of outputs is determined by the gaps between outputs, which are essentially determined by the size of a filter pattern. Longer filter patterns than ours, Eq. (<ref>), can be subjected to a similar analysis, see Fig. <ref> and Table <ref>. 

Longer filter patterns, which give less information about the input string, indeed produce less informative degeneracy distributions (i.e. having lower entropy).

For the sake of simplicity, we studied inputs containing only zeroes 
 and ones. 
We expect that our approach and the mean-field theory should be applicable to more rich inputs containing more degrees of freedom: larger sets of numbers, vectors, etc., as well as to more general cooperative systems with a large number of local minima. 
The next natural step after the mean field theory, namely a fluctuation theory, should be based on accounting for small gaps between ones and the fluctuations of the lengths of these gaps.    

In summary, we have presented a representative filtering problem for which we can obtain exact and complete results for the degeneracy distributions. Our methods may be generalized to other filtering and compression problems involving more complex filter patterns and complex, not necessary synthetic, higher dimensional inputs. We believe the qualitative insights gained from studying this system can be applied to information processing problems in general.



This work was supported by National Funds through
FCT–Portuguese Foundation for Science and Technology,
I.P. Project No. IF/00726/2015. R. A. C. acknowledges the FCT grant SFRH/BPD/123077/2016. 
















































































§ RECURSIVE RELATIONS



Here we present the derivations of the expression for the number of different values of degeneracy of outputs produced by complete input data sets, Eq. (<ref>), and the recursions for N(d,n) used in Sec. <ref>.








 §.§ Derivation of Eq. (<ref>) for M(n)




The total number M(n) of different outputs in our problem is the number of all possible periodic (period n) combinations of zeroes and ones having no neighboring ones. 
Clearly, this number coincides with the total number of different combinations of dimers in a ring of length n. 


To find the number of different outputs with k ones, that is, the number of ways of placing k dimers in the ring, 
it is convenient to consider the cases when the first output digit is 1 and when it is 0 separately. 
This is equivalent to fixing the state of two chosen neighboring units: either there is a dimer connecting this pair or this dimer is absent.

(i) When the first digit of an output is 1, both the second and the last digits must be 0, and the number of outputs in this case is given by the binomial coefficient n-k-1k-1, which corresponds to starting with the sequence 1,{0}_n-k (where {0}_n-m is a sequence of n-m zeroes), 
and choosing k-1 out of n-k-1 distinct zeroes 
 to be replaced by 01. 
Due to the periodic boundary condition, the last 0 cannot be selected for replacement, hence the number of zeroes that can be replaced is n-k-1.

(ii) When the first digit of an output is 0, we start from the sequence {0}_n-k and replace k zeroes 
 by 01. 
In this case the replacement may be made at any of the n-k zeroes, 
and the number of outputs is n-kk. 

The total number of different outputs is obtained by summing these two contributions


    N(k) 
    = n-k-1k-1 + n-kk = n/n-kn-kk
    ,

where we used the notation N(k) from Sec. <ref>.

Summing over all possible values of k gives


    M(n)     =      1+ ∑_k=1^[n/2][ (n-k-1)!/(k-1)!(n-2k)! + (n-k)!/k!(n-2k)!] 
    
    
        =     n ∑_k=0^[n/2]1/n - kn - k  k
    ,


i.e., Eq. (<ref>). 











 §.§ Recursions for N(d,n)




Chains of exactly three zeroes in the output have no degrees of freedom in the input; they can only be produced in one way. Thus outputs containing no chains of zeroes of length greater than three have degeneracy 1.

For the input size n, the number of such outputs, N(d,n), can be obtained recursively. 
Here we derive the recursive relation for N(1,n), N(2,n), and N(4,n), and indicate the recursions for higher degeneracy d. See also Supplementary Material <cit.>.

Sequences of degeneracy 1 can be regarded as assortments of three kinds of building blocks, 01, 001, and 0001, put together in a ring of length n. 
All configurations of blocks are allowed, as long as the total number of binary digits is n.
Let us consider a particular position i in the ring and the block to which i belongs.
If we add a block 01 between the block of i and one of its neighbor blocks (say, the one to the right) to every possible configuration of length n-2, we get every possible configuration of length n that has a block 01 to the right of the block of i. 
Doing the same with configurations of length n-3 and blocks 001, we get all configurations with a block 001 to the right of the block of i. 
Finally, repeating the procedure for configurations of length n-4 and blocks 0001, gives all configurations with a block 0001 to the right of the block of i.
Since every block must be 01, 001, or 0001, the union of these three sets is the full set of configurations of degeneracy 1 in system of n digits.
Thus, for the number of configurations in this set, N(1,n), we can write


    N(1,n) =  N(1,n-2) +  N(1,n-3) +  N(1,n-4)
    .


The explicit solution of this linear difference equation is given in terms of the roots, z_1, z_2,  z_3, and z_4, of the characteristic equation z^4 = z^2 + z +1:

 
    N(1,n) = z_1^n + z_2^n + z_3^n + z_4^n
    ,


where the coefficients of the powers of the roots z_i are found through the initial condition, 

 
    N(1,1)=0,   N(1,2)=2,   N(1,3)=3,   N(1,4)=6
    ,


and are equal to 1. The root z_1 ≡ z_a = 1.46557... determines the large n asymptotics of N(1,n), Eq. (<ref>).

We can expand the analysis to higher values of degeneracy.
For example, the second smallest value, d_2=2, corresponds to the outputs with blocks of the types 01, 001, and 0001 and a single string 00001.
Applying the same reasoning as above, we get three terms similar to the ones of Eq.(<ref>).
We must, additionally, consider configurations with degeneracy 1, to which we add a string 00001 in the same way, instead of one of the other blocks.
Then we get


    N(2,n) =  N(2,n-2) +  N(2,n-3) +  N(2,n-4)
     +  N(1,n-5)


with the initial condition 


    N(2,1)= N(2,2)= N(2,3) =  N(2,4) = 0,    N(2,5)=5
    .


In a similar way, taking into account that the prime degeneracy d̃(ℓ) correspond to the inserted block of ℓ+1 (chain of ℓ zeroes and 1 on the right), i.e., 2, 4, 7, 12, 21, 37, 65, ... correspond to ℓ+1=5,6,7,8,9,10,11,..., respectively, we derive the recursion relations for higher N(d,n) [here d≠ d_D(n), for which, clearly, N(d_D(n),n)=1], 


    N(4,n) =  N(4,n-2) +  N(4,n-3) +  N(4,n-4) 
     +  N(2,n-5) +  N(1,n-6)


with the initial condition 


    N(4,1)=...= N(4,5)=0,   N(4,6)=6
    ,


and so on.  
See the list of all recursive relations for d<100 with initial conditions 
in the Supplementary Material <cit.>. 

The corresponding large n asymptotics are 


    N(1,n)    ≅ z_a^n
    ,
    
     N(2,n)    ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n = 0.05376 n z_a^n
    ,
    
     N(4,n)    ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n
    = 0.001445 n^2 z_a^n
    ,


and so on. See the list of the resulting large n asymptotics of N(d<100,n)  
in the Supplementary Material <cit.>. 


More generally, for any value of degeneracy d one can write the recursion relation for N(d,n) in terms of the multiplicative partition of d into prime degeneracies. 

Let us present the full set of recursion relations for N(d,n). The reasoning is as follows. 

(i) The recursion relation for N(1,n) is given by Eq. (<ref>) with the initial condition Eq. (<ref>).  

(ii) For the largest degeneracies, N(d_D(n),n)=1. 

(iii) All prime degeneracies d̃(ℓ) except d̃(5)=4 are not multiplicatively separable into other prime degeneracies (primality property). The only exception is d̃(5)=d̃^2(4)= 2^2. See Sec. <ref> above for more detail. 

(iv) Any degeneracy in the spectrum except d_D (and d=1) is 
multiplicatively separable into the prime degeneracies d̃(ℓ), namely, 


    d    = d̃^ μ_4(4)d̃^ μ_5(5)d̃^ μ_6(6)d̃^ ν_7(7) 
    ... 
       = 2^ μ_4 4^ μ_5 7^ μ_6 12^ μ_7 
    ... 
       = 2^ μ_4+2μ_5  7^ μ_6 12^ μ_7 
    ...
    ,


where the powers μ_ℓ≡μ(ℓ) are non-negative integers. 
Due to the exception d̃(5)=d̃^2(4)= 2^2 and the coincidence d̃(5)d̃(8)=4×21=7×12=d̃(6)d̃(7), etc., the multiplicative partition into the prime degeneracies d̃(ℓ), Eq. (<ref>), 
may not be unique, see below. 
With all possible integers μ(4)≥ 0, 
μ(6)≥ 0, μ(7)≥ 0 ... we generate the full list D of all degeneracies except 1 and d_D in the spectrum for n→∞. 
We place the generated degeneracies in ascending order, ignoring repetitions for some degeneracies. 
For a finite n, only some on the degeneracies from this list are present in the spectrum. In practice, we need degeneracies d only up to some, maybe, large but finite value. So, generating this list, we use a finite set of non-negative integers μ_4,μ_6,μ_7,... respectively restricted from above. 

(v) For any degeneracy d in this list D we define the vector L(d) ≡ (ℓ_1,ℓ_2,...,ℓ_max), indicating that the prime degeneracies (d̃(ℓ_1),d̃(ℓ_2),...,d̃(ℓ_max)), given in ascending order, are present in at least one of 
the partitions of d, Eq. (<ref>). 
That is, if a prime partition d̃(ℓ) is present in L(d), then the ratio d/d̃(ℓ) also belongs to D.
Then the recursion relation for N(d,n) has the form 


    N(d,n) =  N(d,n-2) +  N(d,n-3) +  N(d,n-4) 
    
     + ∑_ℓ∈ L(d) N(d/d̃(ℓ),n-ℓ-1)
    ,


where ℓ in the sum takes the values ℓ_1,ℓ_2,...,ℓ_max, i.e., the components of the vector L(d). 
This formula sums the number of configurations N(d/d̃(ℓ),n-ℓ-1) of smaller systems to which a block of ℓ zeros (followed by a one) can be added in order to form a configuration of size n and degeneracy d.
We should not explicitly include in this sum configurations that achieve degeneracy d by inserting more than one block of zeros. The insertion of additional blocks besides a block of length l, say, into smaller configurations are already accounted for in the calculation of the degeneracy of the configuration of size n-ℓ-1 into which the block of length l will be inserted.
Note that the ratio d/d̃(ℓ) in each of the terms in the sum is one of the degeneracies, smaller than d, in the list D with the degeneracy d=1 added, so this set of recursions together with the recursion for N(1,n), Eq. (<ref>), is closed.   
The initial conditions for these recursions are 


    N(d,1)    = ... =  N(d,ℓ_max) = 0, 
     N(d,ℓ_max+1)    = (ℓ_max+1)δ(d,d̃(ℓ_max))
    ,


where δ(i,j) is the Kronecker symbol. 
Note than when d is a prime degeneracy d=d̃(ℓ)=d̃(ℓ_max) except d=4=d̃(5), the sum on the left-hand side of Eq. (<ref>) has only one term, N(1,n-ℓ_max-1). 
If d=4, Eqs. (<ref>) and (<ref>) properly give the recursion for from Eq. (<ref>) with the initial condition from Eq. (<ref>). Finally, for d=1, use Eq. (<ref>) with the initial condition Eq. (<ref>). [In fact, if d=1, the list L(d=1) is empty, and Eq. (<ref>) is reduced to Eq. (<ref>). We still need the initial condition, Eq. (<ref>), for d=1, since Eq. (<ref>) is not defined in this case.]

(vi) Equations (<ref>), (<ref>) and (<ref>), (<ref>), in particular, provide all degeneracies present in the spectrum for a given n. If some d is absent, these recursions produce N(d,n)=0. 
For instance, let d=64. The initial condition is N(64,1)=...= N(64,6)=0. The recursions produce N(64,7)=...= N(64,17)=0, N(64,18)=6, N(64,19)=0, N(64,20)=20, 
and so on. 

(vii) Our recursions, Eq. (<ref>), with their initial conditions, Eq. (<ref>), lead to the following large n asymptotics of N(d,n): 


    N(d,n) 
    ≅1/∏_ℓ≠5μ_ℓ ![ n/z_a(2z_a^2 + 3z_a + 4)]^∑_ℓ≠5μ_ℓ  z_a^n - ∑_ℓ≥6(ℓ-4)μ_ℓ


for d with the multiplicative partition into prime degeneracies, Eq. (<ref>), chosen in such a way that the power of 2, μ_4, in this partition is maximal. 

Let us discuss this point in more detail. We stressed above that a multiplicative partition of d∈ D, Eq. (<ref>), may not be unique. For large n, the contribution of each of the possible multiplicative partitions of d to N(d,n) is about n^∑_ℓμ_ℓ  z_a^n - ∑_ℓ(ℓ-4)μ_ℓ. 
The leading asymptotics, Eq. (<ref>), is with the maximal power of n, i.e., it originates from the partition with the maximal sum ∑_ℓμ_ℓ. 

Let us check whether the multiplicative partition of d with the maximal sum ∑_ℓμ_ℓ is unique and that this maximum corresponds to the maximal μ_4. In other words, if there exist a number of different multiplicative partitions of d, that only one of them has the maximal μ_4, and that this partition has the maximal sum ∑_ℓμ_ℓ. 



To explain why the property of primality is very likely to hold for all large enough d̃(ℓ), let us consider the number of conventional prime numbers smaller than some number d, which grows as ∼ d/lnd. 
Since d̃(ℓ) ∼ z_d^ℓ, the number of conventional primes smaller than d̃(ℓ) grows exponentially with ℓ as ∼ z_d^ℓ/ℓ. 
Additionally, the average number of conventional primes in the factorization of numbers of the magnitude of d grows as ∼lnln d <cit.>. 
A necessary condition for some d̃(ℓ) to not be prime is that all of its prime factors are also factors of at least another d̃ < d̃(ℓ).
The combination of the exponential increase of conventional primes smaller than d̃(ℓ), and the increase of the number of factors of d̃(ℓ) as ℓ increases, makes the probability of the degeneracy d̃(ℓ) not being prime approach 0 very rapidly.
In the set of values d̃(ℓ≤ 200), the only ones that do not contain at least one conventional prime factor absent from all factorizations of smaller d̃ are d̃(5)=4, d̃(8)=21, d̃(12)=200, d̃(13)=351, and d̃(24)=170  625, and from these only d̃(5) is actually not a prime degeneracy.

We inspected all products of prime degeneracies 
d̃(ℓ≤200)≈ 1.7  10^48  
e focusing on the products producing non-unique multiplicative partitions. Apart from 2^2=4 discussed above, we find only three such combinations with ℓ≤200 (into this number, we do not include the products of these combinations and arbitrary prime degeneracies). Namely, 2^2 ×21=7× 12, 2^9× 200× 351^2 = 12^6× 65^2, and  2^2×  12^2× 170625 =7 × 200^2 × 351. For each of these combinations we confirm that the left side  of the equality corresponds to the maximal ∑_ℓμ_ℓ and that this partitions is unique. Clearly, the same is true for the products of these combinations and arbitrary prime degeneracies. Thus partitions contributing to the leading asymptotics of N(d,n) are unique, and the gauge is fixed by demanding μ_4=max, which leads to Eq. (<ref>).  
For grasping the form of Eq. (<ref>), see also Eqs. (<ref>), especially the asymptotics of N(84,n).

Thus we have the chain of conveniently coupled linear recursion relations that one can easily process starting from d=1. These recursions generate exact N(d,n) for finite d and n, and in this sense provide the exact solution of the problem. 
Moreover, the leading large n asymptotics of N(d,n) are found explicitly. 
Note that the time of computing all N(d<d_0,n), where d_0 is fixed, by using our recursions, is proportional to n, i.e. the computation for each next size takes the same time.  





§ MOMENTS OF N(D,N)



Here we list the large n asymptotics of the moments of N(d,n). 
The leading asymptotics of the moments are of the following form:   


    M_k(n) ≡∑_i=1^D d_i^k  N(d_i,n) ≅ c_k^n 
    ,


where 


    c_0     =     z_g 
    , 
    
     
    c_1     =     2 
    , 
    
     
    c_2     =     3.13899009933542 
    , 
    
     
    c_3     =     5.41762864130976 
    , 
    
     
    c_4     =     9.48696631140060 
    , 
    
     
    c_5     =     16.6438119672308 
    , 
    
     
    c_6     =     29.2067717071942 
    , 
    
     
    c_7     =     51.2540583046806 
    , 
    
     
    c_8     =     89.9445429351823 
    , 
    
        ...


In their turn, the numbers c_k have the following large k asymptotics: 


    c_k ≅ z_d^k [1 + (z_d^4 - 2)^-k + 
     ...]
    ,


which is close to the numerical values listed above, Eq. (<ref>), already for k=2. The leading term z_d^k results from the largest degeneracy in the spectrum, N(d_D≅ z_d^n,n)=1, the next term originates from the second largest degeneracy, etc.






§ ASYMPTOTIC MEAN-FIELD DEGENERACY DISTRIBUTION


Let us obtain an explicit formula for the asymptotics of the mean-field approximation to the degeneracy distribution N in terms 
of the degeneracy d. We simply replace m in Eq. (<ref>) by the inverse of the function d(m) in Eq. (<ref>). 
The inverse function is m(d)=(ln d - n ln z_d)/(ln C_1- ln z_d) (where we have dropped the bar because d is now the independent variable), and substituting into Eq. (<ref>) gives


    N    =    n/n-mn-mm≈n^m/m!
        =    n ln n/ln (z_d/C_1)/Γ[ 1 - ln (d/z_d^n)/ln (z_d/C_1)]   d^-ln n/ln (z_d/C_1)


for m≪ n. 
Note that the logarithmic derivative of N over d at the point d_D (the highest degeneracy), 
-ln n/ln(z_d^4-2), properly fits the two rightmost points of the spectrum, namely d_D(n) ≅ z_d^n, N(d_D) = 1 and d_D-1(n) ≅ z_d^n/(z_d^4 - 2), 
N(d_D-1) = n. 












33
fxundefined [1]
 ifx#1

fnum [1]
 #1firstoftwo
 secondoftwo
 
fx [1]
 #1firstoftwo
 secondoftwo
 





noop [0]secondoftwo

ref[1]@startlink#1@href
href[1]#1@endlink
anitize@url [0]`
12`$12`&12`#12`1̂2`_12`%12
startlink[1]
endlink[0]

rl [1]href #1












@bib@innerbibempty

[Borda(2011)]borda2011fundamentals
  author author M. Borda, @noop  title Fundamentals in
  Information Theory and Coding (publisher Springer, Berlin,  year 2011)NoStop
[Hankerson et al.(2003)Hankerson, Harris, and Johnson Jr.]hankerson2003introduction
  author author D. C. Hankerson, author G. A. Harris,  and author P. D. Johnson Jr., @noop  title Introduction to
  Information Theory and Data Compression (publisher CRC
  Press, New York, year 2003)NoStop
[Tishby et al.(2000)Tishby,
  Pereira, and Bialek]tishby2000information
  author author N. Tishby, author F. C. Pereira,
   and author W. Bialek,  title title The information bottleneck
  method, @noop  journal journal arXiv
  preprint physics/0004057  (year 2000)NoStop
[Gehani et al.(2003)Gehani,
  LaBean, and Reif]gehani2003dna
  author author A. Gehani, author T. LaBean,   and author J. Reif, title title Dna-based cryptography, in  @noop  booktitle Aspects of Molecular
  Computing (publisher Springer, year 2003)  p. pages 167NoStop
[Hartmann and Weigt(2005)]hartmann2005phase
  author author A. K. Hartmann and author M. Weigt, @noop  title Phase Transitions in
  Combinatorial Optimization Problems (publisher Whiley-VCH,
  Weinheim, year 2005)NoStop
[Mézard et al.(1987)Mézard, Parisi, and Virasoro]mezard1987spin
  author author M. Mézard, author G. Parisi,
   and author M. Virasoro,  @noop  title Spin Glass Theory and Beyond: An
  Introduction to the Replica Method and Its Applications (publisher World Scientific, Singapore, year
  1987)NoStop
[Keskar et al.(2016)Keskar,
  Mudigere, Nocedal, Smelyanskiy, and Tang]keskar2016large
  author author N. S. Keskar, author D. Mudigere,
  author J. Nocedal, author M. Smelyanskiy,  and author P. T. P. Tang, title title On large-batch training for deep
  learning: Generalization gap and sharp minima, @noop  journal journal arXiv preprint arXiv:1609.04836  (year 2016)NoStop
[Baek et al.(2011)Baek,
  Bernhardsson, and Minnhagen]baek2011zipf
  author author Seung Ki  Baek, author Sebastian  Bernhardsson,  and author Petter Minnhagen, title title Zipf's law unzipped, @noop  journal
  journal New Journal of Physics volume
  13, pages 043004 (year 2011)NoStop
[Song et al.(2017)Song,
  Marsili, and Jo]song2017emergence
  author author J. Song, author M. Marsili,   and author J. Jo, title title Emergence and relevance of criticality
  in deep learning, @noop  journal journal arXiv preprint arXiv:1710.11324  (year
  2017)NoStop
[Cubero et al.(2018a)Cubero, Marsili,  and Roudi]cubero2018minimum
  author author R. Cubero, author M. Marsili,   and author Y. Roudi, title title Minimum description length codes are
  critical, @noop  journal journal
  Entropy volume 20, pages 755
  (year 2018a)NoStop
[Haimovici and Marsili(2015)]haimovici2015criticality
  author author A. Haimovici and author M. Marsili, title title Criticality of
  mostly informative samples: A Bayesian model selection approach,  @noop  journal journal J. Stat. Mech.:
  Theory and Experiment volume 2015, pages P10013 (year 2015)NoStop
[Cubero et al.(2018b)Cubero, Jo,
  Marsili, Roudi, and Song]cubero2018minimally
  author author R. J. Cubero, author J. Jo, author M. Marsili, author
  Y. Roudi,  and author
  J. Song, title title Minimally sufficient representations, maximally
  informative samples and Zipf's law, @noop  journal
  journal arXiv preprint arXiv:1808.00249  (year
  2018b)NoStop
[Song et al.(2018)Song,
  Marsili, and Jo]song2018resolution
  author author J. Song, author M. Marsili,   and author J. Jo, title title Resolution and relevance trade-offs in
  deep learning, @noop  journal journal
  J. Stat. Mech.: Theory and Experiment volume
  2018, pages 123406 (year 2018)NoStop
[Bianconi(2009)]bianconi2009entropy
  author author G. Bianconi, title title Entropy of
  network ensembles, @noop  journal journal Phys. Rev. E volume 79, pages 036114 (year 2009)NoStop
[Bianconi(2007)]bianconi2007statistical
  author author G. Bianconi, title title A statistical
  mechanics approach for scale-free networks and finite-scale networks,  @noop  journal journal Chaos: An
  Interdisciplinary Journal of Nonlinear Science volume
  17, pages 026114 (year 2007)NoStop
[Bashkirov and Vityazev(2000)]bashkirov2000information
  author author A. G. Bashkirov and author A. V. Vityazev, title title Information
  entropy and power-law distributions for chaotic systems, @noop 
  journal journal Physica A volume 277, pages 136 (year
  2000)NoStop
[Dover(2004)]dover2004short
  author author Y. Dover, title title A short account
  of a connection of power laws to the information entropy, @noop 
  journal journal Physica A volume 334, pages 591 (year
  2004)NoStop
[Visser(2013)]visser2013zipf
  author author M. Visser, title title Zipf's law,
  power laws and maximum entropy, @noop  journal
  journal New Journal of Physics volume
  15, pages 043021 (year 2013)NoStop
[sup()]supplementary
  @noop  title Supplementary Material,  howpublished <https://???.com>NoStop
[Marsili et al.(2013)Marsili, Mastromatteo, and Roudi]marsili2013sampling
  author author M. Marsili, author I. Mastromatteo,  and author Y. Roudi, title title On sampling and
  modeling complex systems, @noop  journal journal J. Stat. Mech.: Theory and Experiment volume 2013, pages P09003 (year
  2013)NoStop
[Hoggatt Jr.(1969)]hoggatt1969fibonacci
  author author V. E. Hoggatt Jr., @noop  title Fibonacci and Lucas
  Numbers (publisher Houghton Mifflin, Boston, MA, year 1969)NoStop
[Graham et al.(1994)Graham,
  Knuth, Patashnik, and Liu]graham1994concrete
  author author R. L. Graham, author D. E. Knuth,
  author O. Patashnik,  and  author S. Liu, @noop 
  title Concrete Mathematics: A Foundation for Computer
  Science (publisher Addison-Wesley Publishing Company,
  Reading, Massachusetts, year 1994)NoStop
[Koshy(2019)]koshy2019fibonacci
  author author T. Koshy, @noop  title Fibonacci and Lucas
  Numbers with Applications (publisher John Wiley & Sons,
  Inc., Hoboken, New Jersey, year 2019)NoStop
[Austin and Guy(1978)]austin1978binary
  author author H. C. Austin and author R. Guy,  title title Binary sequences without
  isolated ones, @noop  journal journal
  The Fibonacci Quarterly volume 16, pages 84 (year 1978)NoStop
[enc()]encyclopedia_integer_sequences
  @noop  title The On-Line Encyclopedia of
  Integer Sequences, howpublished
  <https://oeis.org>NoStop
[Andrews(1998)]andrews1998theory
  author author G. E. Andrews, @noop  title The Theory of
  Partitions (publisher Cambridge University Press,
  Cambridge, year 1998)NoStop
[Andrews and Eriksson(2004)]andrews2004integer
  author author G. E. Andrews and author K. Eriksson, @noop  title Integer Partitions  (publisher Cambridge University Press, Cambridge, year 2004)NoStop
[Hardy and Ramanujan(1918)]hardy1918asymptotic
  author author G. H. Hardy and author S. Ramanujan, title title Asymptotic
  formulae in combinatory analysis, @noop  journal
  journal Proc. London Math. Soc. volume
  17, pages 75 (year 1918)NoStop
[Uspensky(1920)]uspensky1920asymptotic
  author author J. V. Uspensky, title title Asymptotic
  formulae for numerical functions which occur in the theory of partitions,  @noop  journal journal Bull. Acad. Sci.
  URSS volume 14, pages 199 (year 1920)NoStop
[Wilf(2000)]wilf2000lectures
  author author H. S. Wilf, @noop  title Lectures on Integer
  Partitions, howpublished
  <https://www.math.upenn.edu/ wilf/PIMS/PIMSLectures.pdf> (year 2000)NoStop
[Clauset et al.(2009)Clauset, Shalizi, and Newman]clauset2009power
  author author A. Clauset, author C. R. Shalizi,  and author M. E. J. Newman, title title Power-law
  distributions in empirical data, @noop  journal
  journal SIAM Review volume 51,  pages 661 (year 2009)NoStop
[Dorogovtsev and Mendes(2003)]dorogovtsev2003evolution
  author author S. N. Dorogovtsev and author J. F. F.  Mendes, @noop  title Evolution
  of Networks: From Biological Nets to the Internet and WWW (publisher Oxford University Press, Oxford, year
  2003)NoStop
[Erdös and Kac(1940)]erdos1940gaussian
  author author P. Erdös and author M. Kac, title title The Gaussian law
  of errors in the theory of additive number theoretic functions,  @noop  journal journal Am. J. Math.  volume 62, pages 738 (year
  1940)NoStop



























































. 









Supplemental Materials: Complex distributions emerging in filtering and compression







§ RECURSIONS AND ASYMPTOTICS FOR N(D<100,N)



Here we show the recursion relations for N(d,n) with degeneracy d up to 100, initial conditions for them, and their large n asymptotics. These formulas are particular cases of Eqs. (A12), (A13), and (A14), respectively. 


    N(1,n) =  N(1,n-2) +  N(1,n-3) +  N(1,n-4) 
    ,
    
           N(2,n) =  N(2,n-2) +  N(2,n-3) +  N(2,n-4)  +   N(1,n-5)
    ,
    
           N(4,n) =  N(4,n-2) +  N(4,n-3) +  N(4,n-4)  +  N(2,n-5) +  N(1,n-6)
    ,
    
           N(7,n) =  N(7,n-2) +  N(7,n-3) +  N(7,n-4) +  N(1,n-7)
    ,
    
           N(8,n) =  N(8,n-2) +  N(8,n-3) +  N(8,n-4) +  N(4,n-5) +  N(2,n-6)
    ,
    
           N(12,n) =  N(12,n-2) +  N(12,n-3) +  N(12,n-4) +  N(1,n-8)
    ,
    
           N(14,n) =  N(14,n-2) +  N(14,n-3) +  N(14,n-4) +  N(7,n-5) +  N(2,n-7)
    ,
    
           N(16,n) =  N(16,n-2) +  N(16,n-3) +  N(16,n-4) +  N(8,n-5) +  N(4,n-6)
    ,
    
           N(21,n) =  N(21,n-2) +  N(21,n-3) +  N(21,n-4) +  N(1,n-9)
    ,
    
           N(24,n) =  N(24,n-2) +  N(24,n-3) +  N(24,n-4) +  N(12,n-5) +  N(2,n-8)
    ,
    
           N(28,n) =  N(28,n-2) +  N(28,n-3) +  N(28,n-4) +  N(14,n-5) +  N(7,n-6)+  N(4,n-7)
    ,
    
           N(32,n) =  N(32,n-2) +  N(32,n-3) +  N(32,n-4) +  N(16,n-5) +  N(8,n-6)
    ,
    
           N(37,n) =  N(37,n-2) +  N(37,n-3) +  N(37,n-4) +  N(1,n-10)
    ,
    
           N(42,n) =  N(42,n-2) +  N(42,n-3) +  N(42,n-4) +  N(21,n-5) +  N(2,n-9)
    ,
    
           N(48,n) =  N(48,n-2) +  N(48,n-3) +  N(48,n-4) +  N(24,n-5) +  N(12,n-6)+  N(4,n-8)
    ,
    
           N(49,n) =  N(49,n-2) +  N(49,n-3) +  N(49,n-4) +  N(7,n-7)
    ,
    
           N(56,n) =  N(56,n-2) +  N(56,n-3) +  N(56,n-4) +  N(28,n-5) +  N(14,n-6)+  N(8,n-7)
    ,
    
           N(64,n) =  N(64,n-2) +  N(64,n-3) +  N(64,n-4) +  N(32,n-5) +  N(16,n-6)
    ,
    
           N(65,n) =  N(65,n-2) +  N(65,n-3) +  N(65,n-4) +  N(1,n-11)
    ,
    
           N(74,n) =  N(74,n-2) +  N(74,n-3) +  N(74,n-4) +  N(37,n-5) +  N(2,n-10)
    ,
    
           N(84,n) =  N(84,n-2) + N(84,n-3) + N(84,n-4) + N(42,n-5) + N(21,n-6) + N(12,n-7) + N(7,n-8) + N(4,n-9)
    ,
    
           N(96,n) =  N(96,n-2) +  N(96,n-3) +  N(96,n-4) +  N(48,n-5) +  N(24,n-6)+  N(8,n-8)
    ,
    
           N(98,n) =  N(98,n-2) +  N(98,n-3) +  N(98,n-4) +  N(49,n-5) +  N(14,n-7)


with the initial conditions 


    N(1,1)=0,   N(1,2)=2,   N(1,3)=3,   N(1,4)=6
    ,
    
           N(2,1)=...= N(2,4)=0,   N(2,5)=5
    ,
    
           N(4,1)=...= N(4,5)=0,   N(4,6)=6
    ,
    
           N(7,1)=...= N(7,6)=0,   N(7,7)=7
    ,
    
           N(8,1)=...= N(8,6)=0
    ,
    
           N(12,1)=...= N(12,7)=0,   N(12,8)=8
    ,
    
           N(14,1)=...= N(14,7)=0
    ,
    
           N(16,1)=...= N(16,6)=0
    ,
    
           N(21,1)=...= N(21,8)=0,   N(21,9)=9
    ,
    
           N(24,1)=...= N(24,8)=0
    ,
    
           N(28,1)=...= N(28,7)=0
    ,
    
           N(32,1)=...= N(32,6)=0
    ,
    
           N(37,1)=...= N(37,9)=0,   N(37,10)=10
    ,
    
           N(42,1)=...= N(42,9)=0
    ,
    
           N(48,1)=...= N(48,8)=0
    ,
    
           N(49,1)=...= N(49,7)=0
    ,
    
           N(56,1)=...= N(56,7)=0
    ,
    
           N(64,1)=...= N(64,6)=0
    ,
    
           N(65,1)=...= N(65,10)=0,   N(65,11)=11
    ,
    
           N(74,1)=...= N(74,10)=0
    ,
    
           N(84,1)=...= N(84,9)=0
    ,
    
           N(96,1)=...= N(96,8)=0
    ,
    
           N(98,1)=...= N(98,7)=0
    .


The corresponding large n asymptotics are 


    N(1,n) ≅ z_a^n
    ,
    
           N(2,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n = 0.05376 n z_a^n
    ,
    
           N(4,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n
    = 0.001445 n^2 z_a^n
    ,
    
           N(7,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n-2
    = 0.02503 n z_a^n
    ,
    
           N(8,n) ≅1/3![ 1/z_a(2z_a^2 + 3z_a + 4)]^3 n^3 z_a^n
    =  0.00002589 n^3 z_a^n
    ,
    
           N(12,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n-3
    = 0.01708 n z_a^n
    ,
    
           N(14,n) ≅[ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n-2
    = 0.001345 n^2 z_a^n
    ,
    
           N(16,n) ≅1/4![ 1/z_a(2z_a^2 + 3z_a + 4)]^4 n^4 z_a^n 
    = 3.480× 10^-7 n^4 z_a^n
    ,
    
           N(21,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n-4
    ,
    
           N(24,n) ≅[ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n-3
    ,
    
           N(28,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^3 n^3 z_a^n-2
    ,
    
           N(32,n) ≅1/5![ 1/z_a(2z_a^2 + 3z_a + 4)]^5 n^5 z_a^n 
    ,
    
           N(37,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n-5
    ,
    
           N(42,n) ≅[ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n-4
    ,
    
           N(48,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^3 n^3 z_a^n-3
    ,
    
           N(49,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n-4
    ,
    
           N(56,n) ≅1/3![ 1/z_a(2z_a^2 + 3z_a + 4)]^4 n^4 z_a^n-2
    ,
    
           N(64,n) ≅1/6![ 1/z_a(2z_a^2 + 3z_a + 4)]^6 n^6 z_a^n 
    ,
    
           N(65,n) ≅1/z_a(2z_a^2 + 3z_a + 4)  n z_a^n-6
    ,
    
           N(74,n) ≅[ 1/z_a(2z_a^2 + 3z_a + 4)]^2 n^2 z_a^n-5
    ,
    
           N(84,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^3 n^3 z_a^n-4
    ,
    
           N(96,n) ≅1/3![ 1/z_a(2z_a^2 + 3z_a + 4)]^4 n^4 z_a^n-3
    ,
    
           N(98,n) ≅1/2![ 1/z_a(2z_a^2 + 3z_a + 4)]^3 n^3 z_a^n-4
    ,
    
          
    ...   
    .









§ TABLES OF EXACT RESULTS FOR COMPLETE INPUT DATA SETS




Table <ref> contains the complete data on the spectrum of degeneracy of outputs for complete input data sets of length n up to n=21, namely  
all pairs { d_i, N_i }, i=1,...,D, where d_i is the i-th value of degeneracy and N_i is the corresponding number of outputs having this degeneracy. 
This data for n=21 is presented in graphical form in Fig. 3 (a,b). 
Table <ref> presents the total number of different values of degeneracy D for each input length n≤ 120. 












































 

