Convolution numbers of binary sequences
by · 2025
Read Convolution numbers of binary sequences by by (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18066.txt.
Introduction
Gregory Constantine and Rodica Constantine study counting patterns from combining binary sequences in a 2025 paper. They define convolution sums for such sequences and look closely at the cyclic case on finite sets. The distributions that appear extend two classic counting families, the Catalan and Narayana numbers, into higher dimensions.
They find a closed form for one-dimensional margins and for some two-way margins in the prime case. That is a step toward grasping the full multi-way distributions. They also explain how a full grasp of these distributions would open a route to attack a famous open problem about special square matrices. The paper is aimed at combinatorics specialists.
Catalog record
| CREATOR | by |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18066
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convolution numbers of binary sequences by Abstract ABSTRACT Convolution sums are introduced and special instances of the cyclic convolution on finite sets is examined in more detail. The distributions that emerge are multidimensional generalizations of the Catalan and Narayana numbers. This work yields a closed form solution for 1-dimensional marginals and certain bivariate marginals in the cyclic prime case. It is explained how a sufficiently high resolution of understanding these multidimensional distributions yields an approach to attack the Hadamard matrix conjecture. AMS 2010 Subject Classification: 11B75, 05B05 Key words and phrases: Group action, probability distribution, paths, autocorrelation, Hadamard designs Proposed running head: Convolution numbers Funded under NIH grants P50-GM-53789, RO1-HL-076157 and an IBM shared University Research Award [email protected] 1. Convolution sums Let G be a group acting on a finite set X , and let R be a ring. We let S be a set of functions from X to R. For \sigma\in G and f,g\in S define the element in R \sigma(f,g):=\sum_{x\in X}f(x)g(\sigma x), and call it the \sigma- convolution of f with g . List the elements of G in some arbitrary but fixed order; when writing \sigma\in G we assume that \sigma varies over the elements of G in this specific order. Consider the vector G(f,g)=(\sigma(f,g):\sigma\in G). Partition S\times S by (f_{1},g_{1})\sim(f_{2},g_{2}) if G(f_{1},g_{1})=G(f_{2},g_{2}). Denote by \{S_{i}\} the resulting equivalence classes. Further write G_{i}=G(f_{i},g_{i}), where (f_{i},g_{i}) is a class representative of S_{i}. Let P be a probability measure on S\times S. Induce a probability measure on \{G_{i}\} by assigning P(G_{i})=P(S_{i}). The numbers P(G_{i}) are called convolution numbers. A case of particular interest occurs when we restrict attention to just \sigma(f,f), which we simply write as \sigma(f); this yields an autocorrelation. We abbreviate G(f,f) by Gf. In this case P is a measure on S and the S_{i} are a partition of S. The overarching goal is to understand this induced probability on \{G_{i}\} , for various G,X,S and R. We refer to [7] for a thorough study of autocorrelation and its many applications to engineering, probability and other applied branches of science. Studies of autocorrelation are implicit in proofs of existence of codes and combinatorial designs as is found in [11] and [9]. 2. Definitions and notation in the cyclic case Of initial interest is the case of G=C_{n}, the cyclic group of order n , and X=C_{n} with cardinality as measure. We take R to be the ring Z of integers. Let S be the set of functions from X to Z that take value 1 on exactly k elements of X and value 0 on exactly n-k elements of X. Elements of S are called 0,1- binary functions of weight k on X . Clearly such functions are in bijection with subsets of X with k elements; evidently the cardinality of S is |S|={n\choose k}. We let G=C_{n} act on X=C_{n} by counterclockwise rotations, as is specified below. It is contextually clear when we interpret C_{n} as a group or as the set on which the group acts, and this distinction is not always explicitly highlighted. We also restrict to the autocorrelated case. [In most, but not all, situations we may assume, without loss, that k\leq\frac{n}{2}.] Write G=C_{n}=\{\sigma_{0}=0,\sigma_{1}=1,\ldots,\sigma_{n-1}=(n-1)\}. Then \sigma_{i} may be interpreted as a rotation of ’distance’ i , in the sense that \sigma_{i}x=x+i (mod n ), for all x\in X=C_{n} . The (periodic) autocorrelation \sigma(f)=\sum_{x\in X}f(x)f(\sigma x) may then be viewed as the number of incidences of f at ’distance’ \sigma . Put a uniform measure on S. Write Gf=(\sigma_{0}(f),\ldots,\sigma_{n-1}(f)). Clearly \sigma_{0}(f)=k, for all f; and \sigma_{i}(f)=\sigma_{n-i}(f), for i\geq 1. It thus suffices to write Gf=(\sigma_{1}(f),\ldots,\sigma_{m}(f)) , where m=\lfloor\frac{n}{2}\rfloor and \lfloor x\rfloor stands for the integer less than or equal to the rational number x . By writing c(n,k;(d_{1},\ldots,d_{m})) for the the number of k- subsets of X with d_{i} incidences at distance i, we may express P(Gf)={n\choose k}^{-1}c(n,k;(\sigma_{1}(f),\ldots,\sigma_{m}(f))). A couple of observations: 1. The number c(n,k;(d_{1},\ldots,d_{m}))=0, unless (d_{1},\ldots d_{m})=(\sigma_{1}(f),\ldots,\sigma_{m}(f)) for some f\in S . Exactly when this number is 0 is a central issue in our undertakings, as is explained in some detail in Section 6. In essence, it is typically possible to find three binary vectors that could be included in the Goethals-Seidel construction. These three vectors uniquely determine what the autocorrelation of the forth binary vector ought to be. The Hadamard matrix construction can only be completed, however, if there exists a binary vector with this latter autocorrelation. 2. We have \sum_{i=1}^{m}d_{i}={k\choose 2}, since for any k- subset we have {k\choose 2} unordered distances available in all. An upward-and-right moving path on the integer lattice starting at (0,0) and ending at (n-k,k) that touches or stays above the line joining (0,0) and ( n-k,k) is, for simplicity, just called a path. Note first that any path may be viewed as a k- subset (and, equivalently, as a 0,1-binary sequence with k ones), by listing the indices of the upward moves as elements of the set. To be specific, an upward move is marked by 1 and a move to the right by 0. We draw further attention to the following useful observation. Lemma The C_{n} -orbit of any binary sequence of length n and weight k contains at least one path. It contains exactly one path if n and k are coprime. Proof This is best seen as follows. The line joining (0,0) and (n-k,k) has slope \frac{k}{n-k} . For any 0-1 sequence s=(s_{i}:1\leq i\leq n) of length n, replace the 0s by \frac{-k}{n-k} and leave the 1s as they are; call the new sequence s^{\prime}=(s_{i}^{\prime}). Calculate the partial sums p_{i} of s^{\prime} by setting p_{1}=s_{1}^{\prime}, and p_{i}=p_{i-1}+s_{i}^{\prime} , 2\leq i\leq n. Let i^{*} be an index for which p_{i^{*}} is a minimum. Apply a cyclic rotation to the original sequence s that places in position 1 the index i^{*}+1. It is evident from this construction, by the choice of i^{*} , that the resulting sequence is in the C_{n} -orbit of s and that it corresponds to a path. When k and n are coprime the index i^{*} is unique; else the path would touch the diagonal line at (h,v) with (h,v)\neq(0,0) or (n-k,k) . Similar right triangles now yield \frac{v}{h}=\frac{k}{n-k}, or vn=k(v+h). Since k and n are coprime this forces k to divide v, but this is not possible because v<k. This ends the proof. [For instance, if s=(0,1,0,0,1,1,0), then its orbit is represented by the shifted sequence (1, 1, 0, 0, 1, 0, 0) which corresponds to a path. Note that s itself does not correspond to a path.] By a descent in a 0,1-binary sequence we mean an occurance of 10 in the sequence. When the binary sequence corresponds to a path, a descent occurs when an upward move is followed by a right move on the path. [It is easy to see, for example, that the sequence (0, 1, 0, 0, 1, 1, 0) has exactly two descents.] An ascent is an occurance of 01 in the sequence. A block of ones in a 0,1-binary sequence is a subsequence of consecutive 1s; it is called a run of ones if it is maximal, by inclusion, with this property. A run of zeros is analogously defined.