Moments of crosscorrelation demerit factors of binary sequences

arXiv:2609.05771 · cs.IT, cs.DM, eess.SP, math.CO, math.IT, math.PR · Submitted 2026-09-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Moments of crosscorrelation demerit factors of binary sequences".

Jane: Here's the gist of the paper. Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor For each positive integer l, we endow the 22l pairs of binary sequences of length l with uniform probability measure and study the distribution of their crosscorrelation demerit factors Sarwate showed that the mean value is always 1 regardless of length l We develop a method for finding an exact formula for the pth central moment (for any positive integer p) as a function of l Formulae for the variance and third central moment (p = 2 and 3) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations Our theory also shows that all the central moments must be strictly positive for p ≥ 2 and l ≥ 3.

Tom: Definition of Key Measures The crosscorrelation demerit factor of f and g is defined as CDF(f, g) = P s∈Z Cf,g(s)2 / Cf,f (0)Cg,g(0) This definition is equivalent to the sum over all shifts of the squared magnitudes of the crosscorrelation values for f with g, SSCC(f, g) = X s∈Z Cf,g(s)2 / l2.

Jane: The mean value of SSCC(f, g) for (f, g) ∈ Pair(l) was found by Sarwate

Sar84, eq. [Tom: (38)] to be l2, which we state in terms of the crosscorrelation demerit factor.

Title and authors: Jane: So we’re looking at the paper titled Moments of crosscorrelation demerit factors of binary sequences by Daniel J Katz and Harmony M Vargas <ref:2609.05771#pg1>

Tom: Yeah, they are focusing on how the moments of these demerit factors change depending on the sequence length l <ref:2609.05771#pg3>

Lu: The core contribution is developing a method to find an exact formula for the pth central moment of SSCC as a function of l for any positive integer p <ref:2609.05771#pg3>

Meng: So they’re not just looking at one or two moments, they’re aiming for a general formula that works for any p <ref:2609.05771#pg3>

Tom: That means they can calculate the variance and third central moment by hand using this formula, but they have to use computers for the fourth through sixth central moments <ref:2609.05771#pg3>

Jane: That distinction is important because it shows that while some statistical properties are analytically tractable, others require more intensive computation <ref:2609.05771#pg3>

Lu: And their theory also shows that all these central moments must be strictly positive if the sequence length l is three or more and the moment p is greater than or equal to two <ref:2609.05771#pg3>

Tom: It’s good they’ve established those positivity results, because you need that for a reliable system design <ref:2609.05771#pg2>

The paper's summary: Jane: The paper summarizes how they use combinatorial arguments involving group actions on partitions to derive this general formula for the pth central moment of SSCC <ref:2609.05771#pg3>

Tom: It’s quite deep math, I’m picturing them using some pretty heavy machinery to get that summation formula over coherent isomorphism classes <ref:2609.05771#pg3>

Lu: The paper reorganizes the formula by using an action of the group Gamma sub p on partitions P to get a summation over coherent isomorphism classes CIsom p and then counts solutions for those classes <ref:2609.05771#pg3>

Meng: So they’re essentially mapping out all these possible ways these sequences can interact statistically across different lengths <ref:2609.05771#pg3>

Tom: It sounds like the complexity comes from characterizing these coherently contributory partitions using display matrices which have specific constraints on their row sums, column sums, and their reduced row echelon form <ref:2609.05771#pg3>

Jane: And they use those display matrices to find the isomorphism classes and then count the solutions for each class, which gives them that summation formula for the pth central moment <ref:2609.05771#pg3>

Lu: For specific cases like p equals two and p equals three, these solution count functions turn out to be polynomials of length one and eight <ref:2609.05771#pg3>

Tom: That’s a nice piece of concrete information; it gives us something tangible to work with when we look at the variance or third central moment <ref:2609.05771#pg2>

The paper's improvements: Jane: The main improvement they are presenting is this explicit characterization of coherently contributory partitions using display matrices <ref:2609.05771#pg3>

Tom: So they’re providing a matrix-based method to find these isomorphism classes, which is essential for calculating those higher moments that we couldn't get by hand <ref:2609.05771#pg3>

Lu: They construct sets A, S, T and U to find representatives of the coherent isomorphism classes CIsom p using this method <ref:2609.05771#pg3>

Meng: So they’re essentially giving us a procedure—a recipe—to find the display matrices for each class in CIsom p, which is necessary for those computer-assisted calculations <ref:2609.05771#pg3>

Tom: That procedure is what allows them to compute the fourth through sixth central moments using Ehrhart theory and counting solutions in hypercubes <ref:2609.05771#pg3>

Jane: So it’s moving from a general theory to a practical tool that lets researchers actually compute the higher moments for sequence lengths where we can't just do it manually <ref:2609.05771#pg3>

Lu: It solidifies the final result, which they state is the formula for the pth central moment of SSCC as X P in CIsom p P CSols P l <ref:2609.05771#pg3>

Conclusion: Tom: So to wrap up, they’re giving us this formula for calculating any central moment of SSCC by summing over all coherent isomorphism classes and counting solutions for each class <ref:2609.05771#pg3>

Jane: That means we get the variance and third central moment calculated by hand, but the fourth through sixth moments come from that computer-assisted calculation using those display matrices <ref:2609.05771#pg3>

Lu: The structure they find is really interesting because it’s based on this matrix-based method for finding those display matrices, which helps define the final result <ref:2609.05771#pg3>

Meng: From an engineering standpoint, having a clear way to find these representatives for each class in CIsom p is what makes the whole calculation feasible at scale <ref:2609.05771#pg3>

Tom: It’s a solid paper on how sequence properties can lead to better design choices for communications and radar because it gives us tools to predict performance metrics based on length l <ref:2609.05771#pg3>

Jane: So, the paper "Moments of crosscorrelation demerit factors of binary sequences" gives us a very specific toolset for analyzing these sequence statistics <ref:2609.05771#pg3>

Lu: It’s a method that links abstract partition theory to concrete calculations involving display matrices, which is pretty neat <ref:2609.05771#pg3>

California State University · University of Nebraska-Lincoln

cs.IT, cs.DM, eess.SP, math.CO, math.IT, math.PR

Submitted: 2026-09-04

Updated: 2026-11-16

Comments: 32 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar The crosscorrelation…

Key concepts

Crosscorrelation Demerit Factor (CDF)
This factor measures how similar two binary sequences are across all possible shifts. It is defined as the sum of the squared magnitudes of their crosscorrelation values normalized by the crosscorrelation at zero shift, indicating sequence similarity.
SSCC
The Sum of Squared Crosscorrelation (SSCC) is a measure related to the CDF, calculated as the sum over all shifts of the squared magnitudes of crosscorrelation values, normalized by l squared. It is used to derive statistical moments for performance analysis.
Central Moments
These are statistical measures that describe the shape and distribution of a data set. The paper derives exact formulas for these moments (like variance and skewness) as functions of the sequence length 'l', which helps in understanding sequence performance.
Coherently Contributory Partitions
These are specific mathematical partitions that characterize how the crosscorrelation demerit factor behaves. They are defined by display matrices with specific constraints, which are essential for calculating higher-order moments through a combinatorial framework.

Terminology

Summary

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor For each positive integer l, we endow the 22l pairs of binary sequences of length l with uniform probability measure and study the distribution of their crosscorrelation demerit factors Sarwate showed that the mean value is always 1 regardless of length l We develop a method for finding an exact formula for the pth central moment (for any positive integer p) as a function of l Formulae for the variance and third central moment (p = 2 and 3) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations Our theory also shows that all the central moments must be strictly positive for p ≥ 2 and l ≥ 3. p. 0

Definition of Key Measures

The crosscorrelation demerit factor of f and g is defined as CDF(f, g) = P s∈Z Cf,g(s)2 / Cf,f (0)Cg,g(0) This definition is equivalent to the sum over all shifts of the squared magnitudes of the crosscorrelation values for f with g, SSCC(f, g) = X s∈Z Cf,g(s)2 / l2. The mean value of SSCC(f, g) for (f, g) ∈ Pair(l) was found by Sarwate [Sar84, eq. p. 1 (38)] to be l2, which we state in terms of the crosscorrelation demerit factor. p. 1

Moments as Functions of Length

The variance of the crosscorrelation demerit factor is given by Theorem 1.2, stating that µl2,(f,g) CDF(f, g) = 4l3 − 6l2 + 2l3⁄l4. p. 1 The third central moment of the crosscorrelation demerit factor is given by Theorem 1. p. 23, which states that µl3,(f,g) CDF(f, g) = 8l4 − 32l3 + 40l2 − 16l⁄l6. p. 1 The fourth through sixth central moments of SSCC are quasipolynomial functions of the sequence length l. p. 2

Combinatorial Framework for Moments

The pth central moment of SSCC is given by Proposition 3.1 as µlp,(f,g) SSCC(f, g) = X P∈CCon(p) CAs(P, =, l). p. 9 The set CCon(p) consists of coherently contributory partitions. p. 8 This formula is reorganized using the group action of Γ(p) to obtain a summation formula over coherent isomorphism classes CIsom(p), yielding µlp,(f,g) SSCC(f, g) = X P∈CIsom(p) P CSols(P, l). p. 5

Characterization of Coherently Contributory Partitions

The set CCon(p) is characterized by display matrices M satisfying specific conditions derived from Lemma 5.13. These conditions include row sums being 2, column sums being positive and even, coherence of the matrix M, and constraints on the reduced row echelon form M′. p. 1

Isomorphism Classes and Solution Counts

The coherent isomorphism classes CIsom(p) are organized by an action of the group Γ(p) on partitions P, yielding a summation formula for the pth central moment. The solution count function CSols(P, l) is defined as CAs(P, =, l). p. 6 For specific cases like p=2 and p=3, the solution count functions for the isomorphism classes are polynomials of length 1 and 8. p. 5

Positivity Results

The moments of the crosscorrelation demerit factor are non-negative, with strict positivity occurring unless specific conditions on l and p are met. Specifically, Theorem 6. p. 21 states that µlp,(f,g) SSCC(f, g) is nonnegative. p. 4

Variance Calculation

The variance of the crosscorrelation demerit factor is calculated using the unique isomorphism class in CIsom(2), leading to Theorem 7.3, which states that µl2,(f,g) SSCC(f, g) = 4l3 − 6l2 + 2l3⁄l4. p. 1

Skewness Calculation

The third central moment of the crosscorrelation demerit factor is calculated using the two isomorphism classes in CIsom(3), leading to Theorem 8.3, which states that µl3,(f,g) SSCC(f, g) = 8l4 − 32l3 + 40l2 − 16l. p. 1

Computer-Assisted Calculations

The fourth through sixth central moments of SSCC are computed using a computer program, which finds display matrices for each coherent isomorphism class and uses Ehrhart theory to count solutions in hypercubes. The results yield Theorems 1. p. 5 p. 54—1.6.

Conclusion on Structure

The paper concludes by describing a matrix-based method for finding isomorphism classes of coherently contributory partitions using display matrices, which is essential for calculating the higher moments. The procedure involves constructing sets T and then identifying a set D that contains exactly one display matrix for each class in CIsom(p).

Final Result Synthesis

The final result synthesizes the calculation into µlp,(f,g) SSCC(f, g) = X P∈CIsom(p) P CSols(P, l). p. 1 This formula is derived from Proposition 4. p. 415.

Finding Isomorphism Classes

The procedure for finding display matrices involves constructing sets A, S, T, and U to find representatives of the coherent isomorphism classes CIsom(p). The set D contains exactly one display matrix for each class in CIsom(p). p. 9 p. 9

Positivity Proof

The proof of Theorem 6.1 shows that µlp,(f,g) SSCC(f, g) is nonnegative by showing that the sum of cardinalities of sets cannot be negative. The existence of a specific partition R for odd p > 1 and l ≥ 3 makes the moment strictly positive. p. 4

Variance Derivation

The variance calculation relies on the unique isomorphism class in CIsom(2) to establish Theorem 7.3.

Skewness Derivation

The third central moment calculation relies on the two isomorphism classes in CIsom(3) to establish Theorem 8.3.

Computer Assistance Summary

A computer program is used to find the fourth through sixth central moments of SSCC, which uses Ehrhart theory and Möbius inversion techniques for counting solutions in hypercubes. The results yield Theorems 1.4—1.6.

Final Summary

The paper concludes by describing a matrix-based method to find display matrices for coherently contributory partitions, which is essential for calculating the higher moments. The final result synthesizes the calculation into µlp,(f,g) SSCC(f, g) = X P∈CIsom(p) P CSols(P, l).

Finding Representatives

The procedure for finding display matrices involves constructing sets A, S, T, and U to find representatives of the coherent isomorphism classes CIsom(p). The set D contains exactly one display matrix for each class in CIsom(p).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI systems can be designed for multi-user asynchronous communications and multiple-input multiple-output radar by leveraging families of binary sequences with low mutual aperiodic crosscorrelation demerit factors.

  2. The system can utilize a method to find an exact formula for the pth central moment of SSCC as a function of sequence length l, allowing for the calculation of variance and third central moments by hand, while higher moments are computed via computer assistance.

  3. The AI can perform performance analysis in phase-modulated communications systems by utilizing measures like the crosscorrelation demerit factor to distinguish between two distinct users regardless of signal delay.

  4. For large sequence lengths l, the system can predict that the vast majority of sequences have crosscorrelation demerit factor close to 1, enabling more robust sequence selection for communication protocols.

  5. The system can calculate the fourth through sixth central moments of SSCC using computer-assisted calculations, providing detailed statistical measures for performance analysis.

  6. The AI can determine that the third central moment of CDF is always right-skewed as long as l greater than 2, which informs modeling choices for communication channel statistics.

Related papers