A Quaternary Legendre Pair of Length 64
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: "A Quaternary Legendre Pair of Length 64".
Jane: Here's the gist of the paper. We construct an explicit quaternary Legendre pair of length 64 and verify its autocorrelations to the best of our knowledge, this is the first reported construction at this length.
Tom: Construction Details The paper defines a quaternary Legendre pair of length 64 by setting Aj = iaj and Bj = ibj using specific exponent strings provided in Table 1 and specifies the digit-to-symbol map where 0 maps to 1, 1 maps to i, 2 maps to-1, and 3 maps to-i.
Jane: The exponent strings for the sequences A and B are explicitly listed in Table 1.
Tom: Autocorrelation Verification The verification process relies on the formula PAF(X, k) = Ne(k, 0) − Ne(k, 2) + iNe(k, 1) − Ne(k, 3), where Ne(k, r) is the count of indices j such that ej − ej+k ≡ r (mod 4).
Title and authors: Jane: We've talked about the results of "A Quaternary Legendre Pair of Length sixty-four" and now let's talk about who did this work <ref:2609.25573#pg1,A Quaternary Legendre Pair of Length 64>. The title itself is quite technical, but it points directly to the kind of math they are doing.
Tom: The authors are Harshit Verma from Yale University. This is a solid affiliation for this kind of deep mathematical construction >
Lu: Harshit Verma’s work fits into the broader context of finding these special algebraic structures, linking them to things like quaternary and binary Hadamard matrices, which he references in his introduction >
Meng: So he's tackling a problem that requires a very specific type of structured sequence generation, not just random data >
Jane: He’s showing that for length sixty-four specifically, this construction works <ref:2609.25573#pg1>. What does that mean compared to the other lengths they mentioned, like twenty-eight or thirty-two <ref:2609.25573#pg1>?
Tom: It means they are finally providing a concrete example at this exact length. The paper notes that Kotsireas and Winterhof found pairs up to length thirty-four but sixty-four was unresolved > <ref:2609.25573#pg1>
Lu: So he’s filling a gap in the literature by providing an explicit construction for this specific even length >
Meng: If we are looking at deployment, having a verified construction for a known length means we can test our hardware mapping against something that is mathematically proven to work on paper first >
Jane: And then we get to the proof part. The paper lays out the exact exponent strings in Table one which defines how the sequences A and B are built from digits like zero, one, two, and three > <ref:2609.25573#pg1>
Tom: That digit-to-symbol map is crucial here: zero maps to one, one maps to i, two maps to minus one, and three maps to minus i >
Lu: Those exponent strings in Table one are the actual blueprint <ref:2609.25573#pg1>. Reading them tells you exactly how those sequences A and B are generated from the base structure >
Meng: It’s a bit dense just reading that notation, but it’s the necessary detail if you want to implement this on a chip >
Jane: So, to summarize this part: they found an explicit quaternary Legendre pair of length sixty-four with specific construction rules and mapping from digits to symbols > <ref:2609.25573#pg1,an explicit quaternary Legendre pair of length 64>
Tom: And those rules are explicitly laid out in Table one which is the key piece of information for anyone trying to replicate this work > <ref:2609.25573#pg1>
The paper's summary: Jane: Now that we know who did it and what they built, let’s get into the main point of the paper. They summarize their findings around Theorem one which states that this explicit pair exists for length sixty-four > <ref:2609.25573#pg1>
Tom: The summary boils down to this: they constructed sequences A and B using specific exponent strings to define them, and then they verified their autocorrelation properties against a formula called PAF >
Lu: The key contribution is showing that the PAF function gives you all the necessary information about the sequence behavior. For length sixty-four it shows zero imaginary parts for shifts up to thirty-two > <ref:2609.25573#pg1>
Meng: So, what’s the real-world implication of those zero imaginary parts? It means these correlations are purely real and predictable, which is a huge win for error correction >
Jane: Exactly. When we talk about error correction codes, we want our checks to be simple and not involve complex numbers that are hard to handle in practical systems >
Tom: The paper also shows consistency checks. They verify the global sum of autocorrelations equals two, which is derived from the length of sixty-four and a shift of zero > <ref:2609.25573#pg1>
Lu: And they verify a polynomial identity involving sequences A and B, which confirms the entire algebraic structure holds together correctly across all shifts >
Jane: So, it’s not just one property they checked; it’s a whole system of checks that proves the pair is valid according to the theory they are using >
Tom: It’s a lot of math to prove, but they've done it explicitly for length sixty-four which is where previous work left an open question > <ref:2609.25573#pg1>
The paper's improvements: Jane: So we know it exists and that they verified the core properties. But what are the suggested improvements? They don’t just stop at finding a pair; they propose how this concept can be used to make things better.
Tom: The first improvement is taking these explicit quaternary Legendre pairs and using them for more cryptographic constructions for error correction codes >
Lu: That's about generating sequences with these specific autocorrelation properties, which allows AI systems to implement more robust encoding schemes that can detect and correct errors with guaranteed performance based on those verified correlations >
Meng: I mean, we’re talking about moving beyond just finding *a* pair to building a system where the pair is a fundamental component of the code structure >
Jane: That’s right. It moves it from a mathematical curiosity to something usable in actual engineering applications >
Tom: The second improvement they suggest is developing hardware acceleration modules for fast computation of those sequence autocorrelations >
Meng: That would be the real implementation hurdle. Mapping that digit-to-symbol map into fixed-point arithmetic circuits so AI systems can do these complex calculations in real time, speeding up decoding significantly >
Lu: It’s about turning the mathematical identities from page two into practical hardware instructions, which is a big leap for representation learning > <ref:2609.25573#pg1>
Jane: And they also suggest creating novel quantum error correction protocols using the algebraic structure of that polynomial identity involving sequences A and B >
Tom: That would be designing new quantum states where those required correlation properties are maintained exactly, potentially leading to more stable quantum computations >
Conclusion: Jane: So we’ve covered the construction of this Quaternary Legendre Pair of Length sixty-four how they proved it through rigorous checks, and the suggested ways to use it for better error correction and hardware implementation <ref:2609.25573#pg1,Quaternary Legendre Pair of Length 64>. To wrap up, what's the final word?
Tom: The main implication is that having an explicit pair at length sixty-four moves the theory into a concrete engineering space where we can design codes with guaranteed performance metrics > <ref:2609.25573#pg1>
Lu: It confirms that these algebraic structures are not just theoretical curiosities but are viable building blocks for more complex systems, whether classical or quantum >
Meng: For deployment, it means we have a verified starting point to build models that handle noise better than they currently do without relying on ad hoc fixes >
Jane: So, this paper sets a new benchmark for explicitly constructing these types of sequences at this length and suggests paths for building faster decoding hardware and even novel quantum error correction protocols >
Tom: Indeed. This explicit construction of the Quaternary Legendre Pair of Length sixty-four is a significant step in making these concepts applicable to real-world systems > <ref:2609.25573#pg1,Quaternary Legendre Pair of Length 64>
Harshit Verma
Department of Computer Science, Yale University
cs.DM, math.CO
Submitted: 2026-09-22
Updated: 2026-10-30
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 72/100
The gist: We construct an explicit quaternary Legendre pair of length 64 and verify its autocorrelations to the best of our knowledge, this is the first reported construction at this length.
Key concepts
- Quaternary Legendre Pair
- This is a specific mathematical structure consisting of two sequences, A and B, of the same length (64 in this case). These sequences are designed with precise mathematical properties related to their correlations. They are fundamental building blocks for creating powerful error-correcting codes.
- Digit-to-Symbol Map
- This is a rule that translates simple input numbers (digits 0, 1, 2, 3) into specific symbols in the sequence (e.g., 0 becomes 1, and -i becomes -i). This mapping is crucial because it defines the actual values of the elements within the sequences A and B.
- Autocorrelation Verification (PAF)
- This is a mathematical test used to check how similar a sequence is to itself when shifted by different amounts. The formula PAF(X, k) calculates this relationship using counts of specific remainders modulo 4. Verifying these autocorrelations confirms the pair has the exact desired correlation properties.
- Polynomial Identity
- This is a relationship between two polynomials, A(z) and B(z), derived from the sequences. The identity states that a specific combination of their products equals another polynomial. This identity serves as a strong consistency check to ensure the constructed pair possesses the required mathematical structure.
Terminology
Summary
We construct an explicit quaternary Legendre pair of length 64 and verify its autocorrelations to the best of our knowledge, this is the first reported construction at this length. p. 0
Construction Details
The paper defines a quaternary Legendre pair of length 64 by setting Aj = iaj and Bj = ibj using specific exponent strings provided in Table 1 and specifies the digit-to-symbol map where 0 maps to 1, 1 maps to i, 2 maps to -1, and 3 maps to -i. The exponent strings for the sequences A and B are explicitly listed in Table 1. p. 1
Autocorrelation Verification
The verification process relies on the formula PAF(X, k) = Ne(k, 0) − Ne(k, 2) + iNe(k, 1) − Ne(k, 3), where Ne(k, r) is the count of indices j such that ej − ej+k ≡ r (mod 4). Applying this formula to the sequences A and B yields Table 2, which shows all imaginary parts are zero for the displayed shifts. p. 1
Consistency Checks
Several consistency checks confirm the pair's validity, including checking the global sum of autocorrelations, which is 0 + 2 = 128 - 2 · 63 = 2. Furthermore, a polynomial identity A(z)A(z−1) + B(z)B(z−1) = 130 − 2 X 63 r z r is verified, where the coefficient of z −k on the left is PAF(A, k) + PAF(B, k), matching the right side's constant coefficient of 128 and every other coefficient of-2.
Sequence Composition Analysis
The first sequence contains 32 entries equal to 1 and 32 equal to −1. The number of occurrences of 1, i, −1, and −i in the second sequence are noted as being 17, 16, 16, and 15 respectively. p. 2 This leads to the observation that X 63 j Aj = (X 63 j Bj) = (17 − 16) + i(16 − 15) = 1 + i.
Implementation Verification
A self-contained Python 3 program is provided to check the pair, which asserts that all 63 nonzero shifts are verified exactly. The program checks the alphabet and lengths, all 63 nonzero shifts separately, shift zero, and both row sums. p. 4 The assertion for the pair B confirms that row sum(B) == (1, 1). p. 4 The program successfully prints PASS: all 63 nonzero shifts verified exactly. p. 4
References
[1] Ilias S. Kotsireas and Arne Winterhof. p. 3 Quaternary Legendre pairs
[2] Ilias S. Kotsireas, Christoph Koutschan, and Arne Winterhof. p. 3 Quaternary Legendre pairs II
[3] Jonathan Jedwab and Thomas Pender. Two constructions of quaternary Legendre pairs of even length
[4] Nikita Lebedev. Quaternary Legendre pairs of lengths 42, 46, 52, 58, 66, 72, and 80
arXiv:2609.25573v1 [cs. p. 0
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
-
improve cryptographic constructions for error correction codes by utilizing explicit quaternary Legendre pairs of length 64 to generate sequences with specific autocorrelation properties, as shown in Table 2. This allows AI systems to implement more robust encoding schemes that can detect and correct errors with guaranteed performance based on the verified correlation identities.
-
develop hardware acceleration modules for fast computation of sequence autocorrelations by directly mapping the
digit-to-symbol map
from Table 1 into fixed-point arithmetic circuits. This would allow AI systems to perform these complex calculations in real-time, speeding up decoding processes significantly beyond current methods. -
create novel quantum error correction protocols by using the algebraic structure of the verified identity (7) involving polynomials A(z) and B(z). This allows AI systems to design and analyze quantum states where the required correlation properties are maintained exactly, potentially leading to more stable quantum computations.
Sources
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns