Daniel J. Katz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Daniel J. Katz has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
Adeebur Rahman
Department of Mathematics, California State University, Northridge, CA, USA
1 shared publicationAllison E. Wong
Calif State Univ, Dept Math, Northridge, CA 91330 USA
1 shared publication- Bernardo M. Abrego
California State University, Northridge
1 shared publication - Chunlei Li
Department of Informatics, University of Bergen, Bergen, Norway
1 shared publication - Courtney M. van der Linden
Department of Mathematics, California State University, Northridge, CA, USA
1 shared publication Eli Moore
Department of Mathematics, California State University, Northridge, CA, USA
1 shared publication
Latest Publications
- 20 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 3181-3193
Limiting Moments of Autocorrelation Demerit Factors of Binary Sequences
Various problems in engineering and natural science demand binary sequences that do not resemble translates of themselves, that is, the sequences must have small aperiodic autocorrelation at every nonzero shift. If f is a sequence, then the demerit factor of f is the sum of the squared magnitudes of the autocorrelations at all nonzero shifts for the sequence obtained by normalizing f to unit Euclidean norm. The demerit factor is the reciprocal of Golay’s merit factor, and low demerit factor indicates low self-similarity of a sequence under translation. We endow the$2^{\ell } $ binary sequences of length$\ell $ with uniform probability measure and consider the distribution of their demerit factors. Earlier works used combinatorial techniques to find exact formulas for the mean, variance, skewness, and kurtosis of the distribution as a function of$\ell $ . These revealed that for$\ell \geq 4$ , the pth central moment of this distribution is strictly positive for every$p \geq 2$ . This article shows that for every p, the pth central moment is$\ell ^{-2 p}$ times a quasi-polynomial function of$\ell $ with rational coefficients. It also shows that, in the limit as$\ell $ tends to infinity, the pth standardized moment is the same as that of the standard normal distribution.- 20 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 3181-3193
Limiting Moments of Autocorrelation Demerit Factors of Binary Sequences
Various problems in engineering and natural science demand binary sequences that do not resemble translates of themselves, that is, the sequences must have small aperiodic autocorrelation at every nonzero shift. If f is a sequence, then the demerit factor of f is the sum of the squared magnitudes of the autocorrelations at all nonzero shifts for the sequence obtained by normalizing f to unit Euclidean norm. The demerit factor is the reciprocal of Golay’s merit factor, and low demerit factor indicates low self-similarity of a sequence under translation. We endow the$2^{\ell } $ binary sequences of length$\ell $ with uniform probability measure and consider the distribution of their demerit factors. Earlier works used combinatorial techniques to find exact formulas for the mean, variance, skewness, and kurtosis of the distribution as a function of$\ell $ . These revealed that for$\ell \geq 4$ , the pth central moment of this distribution is strictly positive for every$p \geq 2$ . This article shows that for every p, the pth central moment is$\ell ^{-2 p}$ times a quasi-polynomial function of$\ell $ with rational coefficients. It also shows that, in the limit as$\ell $ tends to infinity, the pth standardized moment is the same as that of the standard normal distribution.- 14 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 3194-3202
Sequences With Identical Autocorrelation Functions
Aperiodic autocorrelation is an important indicator of performance of sequences used in communications, remote sensing, and scientific instrumentation. Knowing a sequence’s autocorrelation function, which reports the autocorrelation at every possible translation, is equivalent to knowing the magnitude of the sequence’s Fourier transform. The phase problem is the difficulty in resolving this lack of phase information. We say that two sequences are equicorrelational to mean that they have the same aperiodic autocorrelation function. Sequences used in technological applications often have restrictions on their terms: they are not arbitrary complex numbers, but come from a more restricted alphabet. For example, binary sequences involve terms equal to only +1 and −1. We investigate the necessary and sufficient conditions for two sequences to be equicorrelational, where we take their alphabet into consideration. There are trivial forms of equicorrelationality arising from modifications that predictably preserve the autocorrelation, for example, negating a binary sequence or reversing the order of its terms. By a search of binary sequences up to length 44, we find that nontrivial equicorrelationality among binary sequences does occur, but is rare. An integer n is said to be equivocal when there are binary sequences of length n that are nontrivially equicorrelational; otherwise n is unequivocal. For $n \leq 44$ , we found that the unequivocal lengths are 1–8, 10, 11, 13, 14, 19, 22, 23, 26, 29, 37, and 38. We pose open questions about the finitude of unequivocal numbers and the probability of nontrivial equicorrelationality occurring among binary sequences.
- 14 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 3194-3202
Sequences With Identical Autocorrelation Functions
Aperiodic autocorrelation is an important indicator of performance of sequences used in communications, remote sensing, and scientific instrumentation. Knowing a sequence’s autocorrelation function, which reports the autocorrelation at every possible translation, is equivalent to knowing the magnitude of the sequence’s Fourier transform. The phase problem is the difficulty in resolving this lack of phase information. We say that two sequences are equicorrelational to mean that they have the same aperiodic autocorrelation function. Sequences used in technological applications often have restrictions on their terms: they are not arbitrary complex numbers, but come from a more restricted alphabet. For example, binary sequences involve terms equal to only +1 and −1. We investigate the necessary and sufficient conditions for two sequences to be equicorrelational, where we take their alphabet into consideration. There are trivial forms of equicorrelationality arising from modifications that predictably preserve the autocorrelation, for example, negating a binary sequence or reversing the order of its terms. By a search of binary sequences up to length 44, we find that nontrivial equicorrelationality among binary sequences does occur, but is rare. An integer n is said to be equivocal when there are binary sequences of length n that are nontrivially equicorrelational; otherwise n is unequivocal. For $n \leq 44$ , we found that the unequivocal lengths are 1–8, 10, 11, 13, 14, 19, 22, 23, 26, 29, 37, and 38. We pose open questions about the finitude of unequivocal numbers and the probability of nontrivial equicorrelationality occurring among binary sequences.
- 1 September 2024
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 93 (4) , 1021-1065
Moments of autocorrelation demerit factors of binary sequences
- 1 September 2024
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 93 (4) , 1021-1065
Moments of autocorrelation demerit factors of binary sequences
- Open Access
- 17 May 2024
- Published by Elsevier in Journal of Number Theory
- Vol. 262, 541-576
Rationality of four-valued families of Weil sums of binomials
- 17 May 2024
- Published by Elsevier in Journal of Number Theory
- Vol. 262, 541-576
Open AccessRationality of four-valued families of Weil sums of binomials
- 1 July 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (12) , 8251-8267
Sequence Pairs With Lowest Combined Autocorrelation and Crosscorrelation
Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair $(f,g)$ of binary sequences (i.e., sequences with terms in {−1, 1}). If $f$ is a nonzero sequence, then its autocorrelation demerit factor, $\text {ADF}(f)$ , is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing $f$ to have unit Euclidean norm. If $(f,g)$ is a pair of nonzero sequences, then their crosscorrelation demerit factor, $\text {CDF}(f,g)$ , is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both $f$ and $g$ to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of $\text {CDF}(f,g)$ and the geometric mean of $\text {ADF}(f)$ and $\text {ADF}{(g)}$ must be at least 1. For randomly selected pairs of long binary sequences, this quantity is typically around 2. In this paper, we show that Pursley and Sarwate’s bound is met for binary sequences precisely when $(f,g)$ is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families.
- 1 July 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (12) , 8251-8267
Sequence Pairs With Lowest Combined Autocorrelation and Crosscorrelation
Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair $(f,g)$ of binary sequences (i.e., sequences with terms in {−1, 1}). If $f$ is a nonzero sequence, then its autocorrelation demerit factor, $\text {ADF}(f)$ , is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing $f$ to have unit Euclidean norm. If $(f,g)$ is a pair of nonzero sequences, then their crosscorrelation demerit factor, $\text {CDF}(f,g)$ , is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both $f$ and $g$ to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of $\text {CDF}(f,g)$ and the geometric mean of $\text {ADF}(f)$ and $\text {ADF}{(g)}$ must be at least 1. For randomly selected pairs of long binary sequences, this quantity is typically around 2. In this paper, we show that Pursley and Sarwate’s bound is met for binary sequences precisely when $(f,g)$ is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families.
- 16 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (5) , 3455-3473
Peak Sidelobe Level and Peak Crosscorrelation of Golay–Rudin–Shapiro Sequences
Sequences with low aperiodic autocorrelation and crosscorrelation are used in communications and remote sensing. Golay and Shapiro independently devised a recursive construction that produces families of complementary pairs of binary sequences. In the simplest case, the construction produces the Rudin–Shapiro sequences, and in general it produces what we call Golay–Rudin–Shapiro sequences. Calculations by Littlewood show that the Rudin–Shapiro sequences have low mean square autocorrelation. A sequence’s peak sidelobe level is its largest magnitude of autocorrelation over all nonzero shifts. Høholdt, Jensen, and Justesen showed that there is some undetermined positive constant$A$ such that the peak sidelobe level of a Rudin–Shapiro sequence of length$2^{n}$ is bounded above by$A(1.842626\ldots)^{n}$ , where$1.842626\ldots $ is the positive real root of$X^{4}-3 X-6$ . We show that the peak sidelobe level is bounded above by$5(1.658967\ldots)^{n-4}$ , where$1.658967\ldots $ is the real root of$X^{3}+X^{2}-2 X-4$ . Any exponential bound with lower base will fail to be true for almost all$n$ , and any bound with the same base but a lower constant prefactor will fail to be true for at least one$n$ . We provide a similar bound on the peak crosscorrelation (largest magnitude of crosscorrelation over all shifts) between the sequences in each Rudin–Shapiro pair. The methods that we use generalize to all families of complementary pairs produced by the Golay–Rudin–Shapiro recursion, for which we obtain bounds on the peak sidelobe level and peak crosscorrelation with the same exponential growth rate as we obtain for the original Rudin–Shapiro sequences.- 16 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (5) , 3455-3473
Peak Sidelobe Level and Peak Crosscorrelation of Golay–Rudin–Shapiro Sequences
Sequences with low aperiodic autocorrelation and crosscorrelation are used in communications and remote sensing. Golay and Shapiro independently devised a recursive construction that produces families of complementary pairs of binary sequences. In the simplest case, the construction produces the Rudin–Shapiro sequences, and in general it produces what we call Golay–Rudin–Shapiro sequences. Calculations by Littlewood show that the Rudin–Shapiro sequences have low mean square autocorrelation. A sequence’s peak sidelobe level is its largest magnitude of autocorrelation over all nonzero shifts. Høholdt, Jensen, and Justesen showed that there is some undetermined positive constant$A$ such that the peak sidelobe level of a Rudin–Shapiro sequence of length$2^{n}$ is bounded above by$A(1.842626\ldots)^{n}$ , where$1.842626\ldots $ is the positive real root of$X^{4}-3 X-6$ . We show that the peak sidelobe level is bounded above by$5(1.658967\ldots)^{n-4}$ , where$1.658967\ldots $ is the real root of$X^{3}+X^{2}-2 X-4$ . Any exponential bound with lower base will fail to be true for almost all$n$ , and any bound with the same base but a lower constant prefactor will fail to be true for at least one$n$ . We provide a similar bound on the peak crosscorrelation (largest magnitude of crosscorrelation over all shifts) between the sequences in each Rudin–Shapiro pair. The methods that we use generalize to all families of complementary pairs produced by the Golay–Rudin–Shapiro recursion, for which we obtain bounds on the peak sidelobe level and peak crosscorrelation with the same exponential growth rate as we obtain for the original Rudin–Shapiro sequences.- 19 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (10) , 6952-6962
The Resolution of Niho’s Last Conjecture Concerning Sequences, Codes, and Boolean Functions
A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length$2^{2m}-1$ with relative decimation$d=2^{m+2}-3$ , where$m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation$f(x)=x^{d}$ over a finite field of order$2^{2m}$ and at most five distinct nonzero weights in the cyclic code of length$2^{2m}-1$ with two primitive nonzeros$\alpha $ and$\alpha ^{d}$ . The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when$m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.- 19 July 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (10) , 6952-6962
The Resolution of Niho’s Last Conjecture Concerning Sequences, Codes, and Boolean Functions
A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length$2^{2m}-1$ with relative decimation$d=2^{m+2}-3$ , where$m$ is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation$f(x)=x^{d}$ over a finite field of order$2^{2m}$ and at most five distinct nonzero weights in the cyclic code of length$2^{2m}-1$ with two primitive nonzeros$\alpha $ and$\alpha ^{d}$ . The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when$m$ is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.- Open Access
An improved uncertainty principle for functions with symmetry
Chebotar\"ev proved that every minor of a discrete Fourier matrix of prime order is nonzero. We prove a generalization of this result that includes analogues for discrete cosine and discrete sine matrices as special cases. We establish these results via a generalization of the Bir\'o-Meshulam-Tao uncertainty principle to functions with symmetries that arise from certain group actions, with some of the simplest examples being even and odd functions. We show that our result is best possible and in some cases is stronger than that of Bir\'o-Meshulam-Tao. Some of these results hold in certain circumstances for non-prime fields; Gauss sums play a central role in such investigations.
Open AccessAn improved uncertainty principle for functions with symmetry
Chebotar\"ev proved that every minor of a discrete Fourier matrix of prime order is nonzero. We prove a generalization of this result that includes analogues for discrete cosine and discrete sine matrices as special cases. We establish these results via a generalization of the Bir\'o-Meshulam-Tao uncertainty principle to functions with symmetries that arise from certain group actions, with some of the simplest examples being even and odd functions. We show that our result is best possible and in some cases is stronger than that of Bir\'o-Meshulam-Tao. Some of these results hold in certain circumstances for non-prime fields; Gauss sums play a central role in such investigations.
- 24 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (12) , 7728-7738
Rudin-Shapiro-Like Sequences With Maximum Asymptotic Merit Factor
Borwein and Mossinghoff investigated the Rudin-Shapiro-like sequences, which are infinite families of binary sequences, usually represented as polynomials. Each family of Rudin-Shapiro-like sequences is obtained from a starting sequence (which we call the seed) by a recursive construction that doubles the length of the sequence at each step, and many sequences produced in this manner have exceptionally low aperiodic autocorrelation. Borwein and Mossinghoff showed that the asymptotic autocorrelation merit factor for any such family is at most 3, and found the seeds of length 40 or less that produce the maximum asymptotic merit factor of 3. The definition of Rudin-Shapiro-like sequences was generalized by Katz, Lee, and Trunov to include sequences with arbitrary complex coefficients, among which are families of low autocorrelation polyphase sequences. Katz, Lee, and Trunov proved that the maximum asymptotic merit factor is also 3 for this larger class. Here we show that a family of such Rudin-Shapiro-like sequences achieves asymptotic merit factor 3 if and only if the seed is either of length 1 or is the interleaving of a pair of Golay complementary sequences. For small seed lengths where this is not possible, the optimal seeds are interleavings of pairs that are as close as possible to being complementary pairs, and the idea of an almost-complementary pair makes sense of remarkable patterns in previously unexplained data on optimal seeds for binary Rudin-Shapiro-like sequences.
- 24 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (12) , 7728-7738
Rudin-Shapiro-Like Sequences With Maximum Asymptotic Merit Factor
Borwein and Mossinghoff investigated the Rudin-Shapiro-like sequences, which are infinite families of binary sequences, usually represented as polynomials. Each family of Rudin-Shapiro-like sequences is obtained from a starting sequence (which we call the seed) by a recursive construction that doubles the length of the sequence at each step, and many sequences produced in this manner have exceptionally low aperiodic autocorrelation. Borwein and Mossinghoff showed that the asymptotic autocorrelation merit factor for any such family is at most 3, and found the seeds of length 40 or less that produce the maximum asymptotic merit factor of 3. The definition of Rudin-Shapiro-like sequences was generalized by Katz, Lee, and Trunov to include sequences with arbitrary complex coefficients, among which are families of low autocorrelation polyphase sequences. Katz, Lee, and Trunov proved that the maximum asymptotic merit factor is also 3 for this larger class. Here we show that a family of such Rudin-Shapiro-like sequences achieves asymptotic merit factor 3 if and only if the seed is either of length 1 or is the interleaving of a pair of Golay complementary sequences. For small seed lengths where this is not possible, the optimal seeds are interleavings of pairs that are as close as possible to being complementary pairs, and the idea of an almost-complementary pair makes sense of remarkable patterns in previously unexplained data on optimal seeds for binary Rudin-Shapiro-like sequences.