Source author record

Daniel J. Katz

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.NT math.CO math.CV Computational Geometry Cryptography and Security Discrete Mathematics

Catalog footprint

Research overview

14works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Almost perfect nonlinear power functions with exponents expressed as fractions

Let $F$ be a finite field, let $f$ be a function from $F$ to $F$ , and let $a$ be a nonzero element of $F$ . The discrete derivative of $f$ in direction $a$ is $Δ_a f \colon F \to F$ with $(Δ_a f)(x)=f(x+a)-f(x)$ . The differential spectrum of $f$ is the multiset of cardinalities of all the fibers of all the derivatives $Δ_a f$ as $a$ runs through $F^*$ . An almost perfect nonlinear (APN) function is one for which the largest cardinality in its differential spectrum is $2$ . Almost perfect nonlinear functions are of interest as cryptographic primitives. If $d$ is a positive integer, then the power function over $F$ with exponent $d$ is the function $f \colon F \to F$ with $f(x)=x^d$ for every $x \in F$ . There is a small number of known infinite families of APN power functions. In this paper, we re-express the exponents for one such family in a more convenient form. This enables us not only to obtain the differential spectrum of each power function $f$ with an exponent in our family, but also to determine the elements that lie in an arbitrary fiber of the discrete derivative of $f$ . This differential analysis, which is far more detailed than previous results, is achieved by composing the discrete derivative of $f$ with some permutations and a double covering of its domain to obtain a function whose fibers can more readily be analyzed.

preprint2022arXiv

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.

preprint2020arXiv

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.

preprint2016arXiv

A New Generating Function for Calculating the Igusa Local Zeta Function

A new method is devised for calculating the Igusa local zeta function $Z_f$ of a polynomial $f(x_1,\dots,x_n)$ over a $p$ -adic field. This involves a new kind of generating function $G_f$ that is the projective limit of a family of generating functions, and contains more data than $Z_f$ . This $G_f$ resides in an algebra whose structure is naturally compatible with operations on the underlying polynomials, facilitating calculation of local zeta functions. This new technique is used to expand significantly the set of quadratic polynomials whose local zeta functions have been calculated explicitly. Local zeta functions for arbitrary quadratic polynomials over $p$ -adic fields with $p$ odd are presented, as well as for polynomials over unramified $2$ -adic fields of the form $Q+L$ where $Q$ is a quadratic form and $L$ is a linear form where $Q$ and $L$ have disjoint variables. For a quadratic form over an arbitrary $p$ -adic field with odd $p$ , this new technique makes clear precisely which of the three candidate poles are actual poles.

preprint2016arXiv

Aperiodic Crosscorrelation of Sequences Derived from Characters

It is shown that pairs of maximal linear recursive sequences (m-sequences) typically have mean square aperiodic crosscorrelation on par with that of random sequences, but that if one takes a pair of m-sequences where one is the reverse of the other, and shifts them appropriately, one can get significantly lower mean square aperiodic crosscorrelation. Sequence pairs with even lower mean square aperiodic crosscorrelation are constructed by taking a Legendre sequence, cyclically shifting it, and then cutting it (approximately) in half and using the halves as the sequences of the pair. In some of these constructions, the mean square aperiodic crosscorrelation can be lowered further if one truncates or periodically extends (appends) the sequences. Exact asymptotic formulae for mean squared aperiodic crosscorrelation are proved for sequences derived from additive characters (including m-sequences and modified versions thereof) and multiplicative characters (including Legendre sequences and their relatives). Data is presented that shows that sequences of modest length have performance that closely approximates the asymptotic formulae.

preprint2016arXiv

On The Number of Similar Instances of a Pattern in a Finite Set

New bounds on the number of similar or directly similar copies of a pattern within a finite subset of the line or the plane are proved. The number of equilateral triangles whose vertices all lie within an $n$ -point subset of the plane is shown to be no more than $\lfloor{(4 n-1)(n-1)/18}\rfloor$ . The number of $k$ -term arithmetic progressions that lie within an $n$ -point subset of the line is shown to be at most $(n-r)(n+r-k+1)/(2 k-2)$ , where $r$ is the remainder when $n$ is divided by $k-1$ . This upper bound is achieved when the $n$ points themselves form an arithmetic progression, but for some values of $k$ and $n$ , it can also be achieved for other configurations of the $n$ points, and a full classification of such optimal configurations is given. These results are achieved using a new general method based on ordering relations.

preprint2015arXiv

Cyclotomy of Weil Sums of Binomials

The Weil sum $W_{K,d}(a)=\sum_{x \in K} ψ(x^d + a x)$ where $K$ is a finite field, $ψ$ is an additive character of $K$ , $d$ is coprime to $|K^\times|$ , and $a \in K^\times$ arises often in number-theoretic calculations, and in applications to finite geometry, cryptography, digital sequence design, and coding theory. Researchers are especially interested in the case where $W_{K,d}(a)$ assumes three distinct values as $a$ runs through $K^\times$ . A Galois-theoretic approach, combined with $p$ -divisibility results on Gauss sums, is used here to prove a variety of new results that constrain which fields $K$ and exponents $d$ support three-valued Weil sums, and restrict the values that such Weil sums may assume.

preprint2015arXiv

Divisibility of Weil Sums of Binomials

Consider the Weil sum $W_{F,d}(u)=\sum_{x \in F} ψ(x^d+u x)$ , where $F$ is a finite field of characteristic $p$ , $ψ$ is the canonical additive character of $F$ , $d$ is coprime to $|F^*|$ , and $u \in F^*$ . We say that $W_{F,d}(u)$ is three-valued when it assumes precisely three distinct values as $u$ runs through $F^*$ : this is the minimum number of distinct values in the nondegenerate case, and three-valued $W_{F,d}$ are rare and desirable. When $W_{F,d}$ is three-valued, we give a lower bound on the $p$ -adic valuation of the values. This enables us to prove the characteristic $3$ case of a 1976 conjecture of Helleseth: when $p=3$ and $[F:{\mathbb F}_3]$ is a power of $2$ , we show that $W_{F,d}$ cannot be three-valued.

preprint2015arXiv

New Open Problems Related to Old Conjectures by Helleseth

Recently, very interesting results have been obtained concerning the Fourier spectra of power permutations over a finite field. In this note we survey the recent ideas of Aubry, Feng, Katz, and Langevin, and we pose new open problems related to old conjectures proposed by Helleseth in the middle of the seventies.

preprint2015arXiv

Proof of a Conjectured Three-Valued Family of Weil Sums of Binomials

We consider Weil sums of binomials of the form $W_{F,d}(a)=\sum_{x \in F} ψ(x^d-a x)$ , where $F$ is a finite field, $ψ\colon F\to {\mathbb C}$ is the canonical additive character, $\gcd(d,|F^\times|)=1$ , and $a \in F^\times$ . If we fix $F$ and $d$ and examine the values of $W_{F,d}(a)$ as $a$ runs through $F^\times$ , we always obtain at least three distinct values unless $d$ is degenerate (a power of the characteristic of $F$ modulo $|F^\times|$ ). Choices of $F$ and $d$ for which we obtain only three values are quite rare and desirable in a wide variety of applications. We show that if $F$ is a field of order $3^n$ with $n$ odd, and $d=3^r+2$ with $4 r \equiv 1 \pmod{n}$ , then $W_{F,d}(a)$ assumes only the three values $0$ and $\pm 3^{(n+1)/2}$ . This proves the 2001 conjecture of Dobbertin, Helleseth, Kumar, and Martinsen. The proof employs diverse methods involving trilinear forms, counting points on curves via multiplicative character sums, divisibility properties of Gauss sums, and graph theory.

preprint2013arXiv

Advances in the merit factor problem for binary sequences

The identification of binary sequences with large merit factor (small mean-squared aperiodic autocorrelation) is an old problem of complex analysis and combinatorial optimization, with practical importance in digital communications engineering and condensed matter physics. We establish the asymptotic merit factor of several families of binary sequences and thereby prove various conjectures, explain numerical evidence presented by other authors, and bring together within a single framework results previously appearing in scattered form. We exhibit, for the first time, families of skew-symmetric sequences whose asymptotic merit factor is as large as the best known value (an algebraic number greater than 6.34) for all binary sequences; this is interesting in light of Golay's conjecture that the subclass of skew-symmetric sequences has asymptotically optimal merit factor. Our methods combine Fourier analysis, estimation of character sums, and estimation of the number of lattice points in polyhedra.

preprint2013arXiv

Littlewood Polynomials with Small $L^4$ Norm

Littlewood asked how small the ratio $||f||_4/||f||_2$ (where $||.||_α$ denotes the $L^α$ norm on the unit circle) can be for polynomials $f$ having all coefficients in $\{1,-1\}$ , as the degree tends to infinity. Since 1988, the least known asymptotic value of this ratio has been $\sqrt[4]{7/6}$ , which was conjectured to be minimum. We disprove this conjecture by showing that there is a sequence of such polynomials, derived from the Fekete polynomials, for which the limit of this ratio is less than $\sqrt[4]{22/19}$ .

preprint2012arXiv

Asymptotic $L^4$ norm of polynomials derived from characters

Littlewood investigated polynomials with coefficients in $\{-1,1\}$ (Littlewood polynomials), to see how small their ratio of norms $||f||_4/||f||_2$ on the unit circle can become as $deg(f)\to\infty$ . A small limit is equivalent to slow growth in the mean square autocorrelation of the associated binary sequences of coefficients of the polynomials. The autocorrelation problem for arrays and higher dimensional objects has also been studied; it is the natural generalization to multivariable polynomials. Here we find, for each $n > 1$ , a family of $n$ -variable Littlewood polynomials with lower asymptotic $||f||_4/||f||_2$ than any known hitherto. We discover these through a wide survey, infeasible with previous methods, of polynomials whose coefficients come from finite field characters. This is the first time that the lowest known asymptotic ratio of norms $||f||_4/||f||_2$ for multivariable polynomials $f(z_1,...,z_n)$ is strictly less than what could be obtained by using products $f_1(z_1)... f_n(z_n)$ of the best known univariate polynomials.

preprint2011arXiv

Proof of a Conjecture of Helleseth: Maximal Linear Recursive Sequences of Period $2^{2^n}-1$ Never Have Three-Valued Cross-Correlation

We prove a conjecture of Helleseth that claims that for any $n \geq 0$ , a pair of binary maximal linear sequences of period $2^{2^n}-1$ can not have a three-valued cross-correlation function.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Daniel J. Katz

Research overview

Is this your work?

14 publications

Almost perfect nonlinear power functions with exponents expressed as fractions

Sequence Pairs with Lowest Combined Autocorrelation and Crosscorrelation

Rudin-Shapiro-Like Sequences with Maximum Asymptotic Merit Factor

A New Generating Function for Calculating the Igusa Local Zeta Function

Aperiodic Crosscorrelation of Sequences Derived from Characters

On The Number of Similar Instances of a Pattern in a Finite Set

Cyclotomy of Weil Sums of Binomials

Divisibility of Weil Sums of Binomials

New Open Problems Related to Old Conjectures by Helleseth

Proof of a Conjectured Three-Valued Family of Weil Sums of Binomials

Advances in the merit factor problem for binary sequences

Littlewood Polynomials with Small $L^4$ Norm

Asymptotic $L^4$ norm of polynomials derived from characters

Proof of a Conjecture of Helleseth: Maximal Linear Recursive Sequences of Period $2^{2^n}-1$ Never Have Three-Valued Cross-Correlation

See the researcher in context

Building this map preview

Daniel J. Katz

Research overview

Is this your work?

14 publications

Almost perfect nonlinear power functions with exponents expressed as fractions

Sequence Pairs with Lowest Combined Autocorrelation and Crosscorrelation

Rudin-Shapiro-Like Sequences with Maximum Asymptotic Merit Factor

A New Generating Function for Calculating the Igusa Local Zeta Function

Aperiodic Crosscorrelation of Sequences Derived from Characters

On The Number of Similar Instances of a Pattern in a Finite Set

Cyclotomy of Weil Sums of Binomials

Divisibility of Weil Sums of Binomials

New Open Problems Related to Old Conjectures by Helleseth

Proof of a Conjectured Three-Valued Family of Weil Sums of Binomials

Advances in the merit factor problem for binary sequences

Littlewood Polynomials with Small L4L^4L4 Norm

Asymptotic L4L^4L4 norm of polynomials derived from characters

Proof of a Conjecture of Helleseth: Maximal Linear Recursive Sequences of Period 22n−12^{2^n}-122n−1 Never Have Three-Valued Cross-Correlation

See the researcher in context

Building this map preview

Littlewood Polynomials with Small $L^4$ Norm

Asymptotic $L^4$ norm of polynomials derived from characters

Proof of a Conjecture of Helleseth: Maximal Linear Recursive Sequences of Period $2^{2^n}-1$ Never Have Three-Valued Cross-Correlation