1 Introduction

1.1 Purpose

Let ℤ denote the ring of integers and let ℂ denote the field of complex numbers. Given an integer N, form the ring ℤ/Nℤ of integers modulo N.

Definition 1.1

Let u:ℤ/Nℤ:→ℂ be an N-periodic sequence. The discrete narrow band ambiguity function, A N (u):ℤ/Nℤ×ℤ/Nℤ→ℂ, is defined to be

$$A_N(u)[m,n]= \frac{1}{N}\sum_{k=0}^{N-1}u[m+k]\overline{u[k]}e^{-2\pi ikn/N}$$

for all (m,n)∈ℤ/Nℤ×ℤ/Nℤ.

The discrete autocorrelation of u is the function A N (u)[⋅,0]:ℤ/Nℤ→ℂ.

The ambiguity function in Definition 1.1 stems from P.M. Woodward’s definition of the narrow band ambiguity function defined on ℝ×ℝ [37].

Definition 1.2

An N-periodic sequence u:ℤ/Nℤ→ℂ is constant amplitude zero autocorrelation (CAZAC) if it satisfies the following properties:

Clearly, C(u)[m]=A N (u)[m,0] for each m∈ℤ/Nℤ. Equation (CA) is the condition that u has constant amplitude 1. Equation (ZAC) is the condition that u has zero autocorrelation.

Our setting is almost exclusively limited to the case that N=p is prime. As such, ℤ/pℤ is a field.

We shall use a remarkable construction of CAZAC sequences u p of prime length p to prove optimal behavior of A p (u p ). The construction is due to Göran Björck [8, 9]. By optimal behavior, we mean that if p is an odd prime, then

$$ |A_p(u_p)[m,n]| < \frac{2}{\sqrt{p}} + \frac{4}{p} \quad\text{for all } (m,n) \in({\mathbb{Z}}/p{\mathbb{Z}}\times{\mathbb{Z}}/p{\mathbb{Z}}) \smallsetminus\bigl\{(0,0)\bigr\},$$
(1)

see Theorem 3.8. By comparison, a short and elementary calculation shows that for any CAZAC u,

$$\max \bigl\{|A_p(u)[m,n]| : (m,n) \in({\mathbb{Z}}/p{\mathbb{Z}}\times {\mathbb{Z}}/p{\mathbb{Z}}) \smallsetminus\bigl\{(0,0)\bigr\} \bigr\} \geq \frac{1}{\sqrt{p-1}},$$

and therefore the bound (1) above is indeed of optimal order of magnitude.

Remark 1.3

The proof of Theorem 3.8 requires André Weil’s exponential sum bound, [35], which is a consequence of his proof of the Riemann Hypothesis for curves over finite fields, [36], announced in the Comptes Rendus in 1940. Further, it seems unlikely that there are more elementary means to prove the inequality (1). In fact, in estimating A p (u p ), the critical term to estimate is a Kloosterman sum; and, if there were an easier way to bound it by \(C/\sqrt{p}\), then there would be an easier way to prove Weil’s bound for Kloosterman sums, which is an essential consequence of [35] and which has withstood the test of time vis a vis evolutionary simplification.

Remark 1.4

Notwithstanding the level of mathematics required to prove the inequality (1), as noted in Remark 1.3, we emphasize that our coding and implementation of Björck’s CAZAC sequences is truly elementary. In this regard, see [7], as well as earlier Björck experiments and constructions by one of the authors, e.g., see [6] and references therein, cf. Remark 1.5. In the parlance of waveform design, Theorem 3.8 is an ideal discrete “thumbtack” narrow band ambiguity function which can be used to design ideal phase-coded waveforms devoid of any substantial time or Doppler coupling in the continuous narrow band ambiguity function plane. With regard to hardware implementation of these phase-coded waveforms (as well as others stemming from low correlation sequences), the power, bandwidth, and hardware requirements will introduce noise. It is understood that modifications must be made to the formulation of a given low correlation sequence to permit implementation while controlling this noise.

1.2 Background

The study of CAZAC sequences and of other sequences related to optimal autocorrelation behavior has origins in several important applications, one of the most prominent being in the general area of waveform design associated with radar and communications, see, e.g., according to year of publication [2, 3, 6, 10–12, 16, 20–22, 24, 25, 27, 31, 33, 34]. There are hundreds of articles in this area and so this selection may seem arbitrary, although several of these references contain focused lists of contributions and specific applications. Also see Remark 1.5.

There are also purely mathematical origins for the construction of CAZAC sequences. One such origin is due to Norbert Wiener, e.g., see new related constructions in [4, 5]. Another may be said to have originated in a question by Per Enflo in 1983. This particular mathematical path has been documented and built upon by Bahman Saffari [28]. Enflo’s question is the following for a given odd prime p. Is it true that the Gaussian sequences, u:ℤ/pℤ→ℂ, defined by

$$u[k]=\zeta_{p}^{rk^{2}+sk},\quad k=0,1,\ldots,p-1,$$

where ζ p =e 2πi/p , r,s∈ℤ and p does not divide r, are the only unimodular sequences of length p, with u[0]=1, whose Discrete Fourier Transform (DFT) has modulus 1? This is equivalent to asking whether such sequences u with u[0]=1 are the only bi-unimodular sequences of odd prime length. Enflo was interested in this because of a problem dealing with exponential sums.

Enflo’s question has a positive answer for p=3 and p=5. In 1984, by computer search, Björck discovered counterexamples to the Enflo question for p=7 and p=11, see [8]. Later in 1985, Björck saw the role of Legendre symbols in his counterexamples, and this led to his theorems in [9]. It also led to a host of mathematical problems, many still unresolved, about the number of CAZAC sequences for a given length, see, [5–7, 14], as well as a several valuable oral and email communications by Saffari [29].

Remark 1.5

(a) It is relevant to mention a striking recent application of low correlation sequences to radar in terms of compressed sensing [17]. In this case, the authors use Alltop sequences [1] Theorem 2, cf. [32] Sect. 2.1.3. It then becomes natural to think in terms of frames generated by Björck sequences for extending the high-resolution radar/compressed sensing setting of the authors of [17].

In fact, the correlation result we prove in Theorem 3.8 is equivalent to the mutual coherence property of finite Gabor frames. This property is reflected by the maximal magnitude of the pairwise inner products of Gabor frame elements. Consequently, Theorem 3.8 can be interpreted as constructing a Gabor frame with essentially optimally low coherence. Naturally, this can lead to its effective numerical implementation using methods such as orthogonal matching pursuit (OMP). This approach is developed in [7].

(b) Another approach to the problem addressed in Sect. 1.1 is found in [13], cf. [23]. The authors obtain bounds comparable to those found herein, but their class of signals, called the oscillator system, is not necessarily ZAC although excellent cross-correlation criteria are obtained, something we have not pursued. More important, from the point of view of application, the characterization and construction of the oscillator system are decidedly representation theoretic. As such an explicit algorithm associated with the collection of split tori in Sp requires a Bruhat decomposition.

(c) The companion, [7], of this paper not only exhibits the simplicity of implementation stressed in Remark 1.4, but also reflects the combinatorial and geometrical complexity in the ambiguity function domain due to the role of the Legendre symbol in defining Björck sequences. Some of this complexity is characterized by intricate Latin and magic square patterns. Further, the simplicity of implementation gives rise to useful, efficient bounds off of small neighborhoods of (0,0) in the ambiguity function domain for compactly supported waveforms on ℝ having p lags whose coefficients are the elements of a Björck sequence u p . Also, it is not difficult to see that, as with the oscillator system, there is Fourier invariance of Björck sequences, most simply calculated in the p≡1(mod 4) case, e.g., [26].

1.3 Outline

We define Björck sequences in Sect. 2. Properties of Kloosterman sums are proven in Sect. 3.1. These, in turn, are used along with Weil’s results and the proper decomposition formula to express Björck sequences in the way that allows us to prove Theorem 3.8 in Sect. 3.2. Section 4 provides figures and data which motivated and guided us.

2 Björck Sequences and Multiplicative Characters

For each prime number p, recall that the Legendre symbol modulo p is the function \(\chi= ( \frac{\cdot}{p} ):{\mathbb{Z}}/p{\mathbb{Z}}\rightarrow\{+1,0,-1\}\) given by

$$\chi[k] = \biggl( \frac{k}{p} \biggr)= \begin{cases}+1 & \text{if } k\equiv m^{2}\ (\mathrm{mod}\ p)\text{ for some } m\in{{\mathbb{Z}}/p{\mathbb{Z}}}^{\times},\\0 & \text{if } k\equiv0\ (\mathrm{mod}\ p),\\-1 & \text{if } k\not\equiv m^{2}\ (\mathrm{mod}\ p)\text{ for all } m\in{{\mathbb{Z}}/p{\mathbb{Z}}}.\end{cases} $$

The preimage of +1 under the Legendre symbol function is the set \(\mathcal{Q}\) of nonzero quadratic residues modulo p; and the preimage of −1 under the Legendre symbol function is the set \(\mathcal{Q}^{C}\) of quadratic nonresidues modulo p. Among the many properties of the Legendre symbol, we shall use the fact that it is a character of the multiplicative group (ℤ/pℤ)×. This means that χ, when restricted to (ℤ/pℤ)×, is a group homomorphism into ℂ×; see [15], Chaps. V and VI.

Definition 2.1

The Björck sequence of length p, where p is a prime and p≡1(mod 4), is defined by

$$u[k]=\exp \bigl( i\theta\chi(k) \bigr) =\exp \biggl( i\theta \biggl( \frac{k}{p} \biggr) \biggr), \quad\text{where }\theta=\arccos \biggl( \frac{1}{1+\sqrt {p}} \biggr),$$

for all k∈ℤ/pℤ.

The Björck sequence of length p, where p is a prime and p≡3(mod 4), is defined by

$$u_{p}[k]= \begin{cases}\exp(i\phi) & \text{if }k\in\mathcal{Q}^{C}\subseteq({\mathbb{Z}}/p{\mathbb{Z}})^{\times},\ \text{where }\phi=\arccos (\frac{1-p}{1+p} ),\\1 & \text{otherwise},\end{cases}$$

for all k∈ℤ/pℤ.

In the case p≡1(mod 4), Definition 2.1 is equivalent to the following definition for the Legendre symbol sequence {0,1,…,−1,…,1} of length p. We replace the first term 0 by 1, every term 1 by

$$\eta= \exp \biggl(i \arccos \frac{\sqrt{p}-1}{p-1} \biggr) = \frac{1}{\sqrt{p}+1} + i\frac{\sqrt{p + 2\sqrt{p}}}{\sqrt{p}+1},$$

and every term −1 by the complex conjugate of η; see [28] for a modest generalization. As proven by Björck and differently in [7], we obtain a CAZAC, and hence bi-unimodular, sequence with three values, viz., 1 at k=0, and η and \(\overline{\eta}\) at k∈(ℤ/pℤ)×.

In the case p≡3(mod 4), Definition 2.1 is equivalent to the following definition for the Legendre symbol sequence {0,1,…,−1} of length p. Replace the first term 0 by 1, and replace every −1 by

$$\xi= \exp \biggl(i \arccos \frac{1-p}{1+p} \biggr)= \frac{1-p}{1+p}+i\frac{2\sqrt{p}}{1+p}.$$

As proven by Björck and differently in [7], we obtain a CAZAC, and hence bi-unimodular, sequence with only two values, viz., 1 and ξ.

3 The Main Theorem

3.1 The Legendre Symbol and Kloosterman Sums

Definition 3.1

Let p be a prime. For any integers a,b, the quantity

$$K[a,b;p] =\sum_{x\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} \exp \bigl(2\pi i\bigl(ax + bx^{-1}\bigr)/p \bigr),$$

where x −1 denotes the multiplicative inverse of x in the field ℤ/pℤ, is a Kloosterman sum.

Kloosterman sums are always real-valued, as the following Lemma states.

Lemma 3.2

Let p be a prime. Then K[a,b;p]∈ℝ for all integers a,b∈ℤ.

Proof

By the substitution y=−x, we have

$$\overline{K[a,b;p]} =\sum_{x\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} e^{-2\pi i (ax + bx^{-1})/p} =\sum_{y\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} e^{2\pi i (ay + by^{-1})/p} =K[a,b;p].$$

 □

The following classical description of certain Kloosterman sums was first observed by Hans Salié in (52) of [30], using a formula of Ernst Jacobsthal from a footnote on page 239 of [19]. Jacobsthal’s footnote refers the reader to his 1906 Ph.D. thesis, but fortunately the proof of his formula is not difficult to derive.

Lemma 3.3

Fix an odd prime p and an integer a not divisible by p. Let \(\chi= (\frac{\cdot}{p} )\) denote the Legendre symbol modulo p.

  1. (a)

    (Jacobsthal, 1907) Let F:ℤ/pℤ→ℂ be any function. Then

    $$\sum_{x\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} F\bigl[x + a x^{-1}\bigr] =\sum_{x=0}^{p-1} F[x] + \sum _{x=0}^{p-1} \chi\bigl[x^2 - 4a\bigr] F[x].$$
  2. (b)

    (Salié, 1932) \(\displaystyle K[1,a;p] = \sum_{x=0}^{p-1} \chi[x^2 - 4a] e^{2\pi i x/p}\).

The formulas of Lemma 3.3 are known, but we include their proofs because of the role they play in our approach.

Proof

(a). Let g:(ℤ/pℤ)×→ℤ/pℤ be the function g[x]=x+ax −1. For each t∈ℤ/pℤ, set

$$N[t] = \mathrm{card} \bigl\{x\in({\mathbb{Z}}/p{\mathbb{Z}})^{\times} : g[x] = t\bigr\}.$$

The desired sum can now be written as

$$\sum_{x\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} F\bigl[x + a x^{-1}\bigr] =\sum_{x\in{\mathbb{Z}}/p{\mathbb{Z}}^{\times}} F \bigl[g[x] \bigr] = \sum _{t\in{\mathbb{Z}}/p{\mathbb{Z}}} N[t] F[t].$$

Thus, it suffices to show that N[t]=1+χ[t 2−4a].

Note that g[x]=g[ax −1]. Conversely, for any x,y∈(ℤ/pℤ)× with g[x]=g[y], we must have either y=x or y=ax −1, since 0=g[x]−g[y]=(x−y)(1−ax −1 y −1). Thus, N[t]≤2 for all t∈ℤ/pℤ, and N[t]=1 if and only if t=g[x] for a point x∈(ℤ/pℤ)× such that x=ax −1. This latter condition occurs if and only if x 2=a in ℤ/pℤ; in that case, t=g[x]=g[ax −1]=2x, or equivalently, t 2=4a. Thus, if we set

$$S = \bigl\{g[x] : x\in({\mathbb{Z}}/p{\mathbb{Z}})^{\times} , x^2\neq a \bigr\},$$

then

$$N[t] = \begin{cases}2 & \text{if } t\in S,\\1 & \text{if } t^2 = 4a,\\0 & \text{otherwise}.\end{cases} $$

Note, on the other hand, that

$$1+\chi\bigl[t^2 - 4a\bigr] = \begin{cases}2 & \text{if } t^2 -4a \text{ is a square in } ({\mathbb{Z}}/p{\mathbb{Z}})^{\times},\\1 & \text{if } t^2 - 4a = 0 \text{ in } {\mathbb{Z}}/p{\mathbb{Z}},\\0 & \text{otherwise}.\end{cases} $$

Thus, it suffices to show that

$$ S = \bigl\{ t\in{\mathbb{Z}}/p{\mathbb{Z}}: t^2 - 4a\text{ is a square in } ({\mathbb{Z}}/p{\mathbb{Z}})^{\times} \bigr\}.$$
(2)

Given t∈S, pick x∈(ℤ/pℤ)× such that t=g[x]. Then

$$t^2 - 4a = \bigl(x+ax^{-1}\bigr)^2 - 4a =x^2 - 2a + a^2 x^{-2} = \bigl(x-ax^{-1}\bigr)^2.$$

In addition, since t 2≠4a for all t∈S, it follows that t 2−4a is a square in (ℤ/pℤ)×, proving the forward inclusion.

Conversely, given t∈(ℤ/pℤ) for which there is some z∈(ℤ/pℤ)× with z 2=t 2−4a, set x=(t+z)/2∈(ℤ/pℤ)×. Then x(x−z)=(t 2−z 2)/4=a, and therefore g(x)=x+ax −1=2x−z=t. It follows that t∈S, proving (2) and hence part (a).

Part (b) is immediate by setting F[x]=e 2πix/p and noting that \(\sum_{x=0}^{p-1} e^{2\pi i x/p} = 0\). □

Theorem 3.4

Fix an odd prime p. Let \(\chi= ( \frac{\cdot}{p} )\) be the Legendre symbol modulo p. Then

$$e^{-\pi i mn/p} A_p(\chi)[m,n]\in{\mathbb{R}}, \quad\text{and}\quad |A_p(\chi)[m,n]| \leq \frac{2}{\sqrt{p}},$$

for all m,n∈ℤ/pℤ∖{0}.

Proof

Fix m,n∈ℤ/pℤ∖{0}. Noting that χ is multiplicative and real-valued, we have

$$A_p(\chi)[m,n] = \frac{1}{p}\sum _{k\in{\mathbb{Z}}/p{\mathbb{Z}}} \chi[k+m]\overline{\chi[k]} e^{-2\pi i kn /p} =\frac{1}{p} \sum_{k\in{\mathbb{Z}}/p{\mathbb{Z}}} \chi \bigl[k(k+m)\bigr] e^{-2\pi i kn /p}.$$

Let a=(mn)2/16, b=m/2, and c=−1/n, where we are doing the arithmetic in ℤ/pℤ. Substituting k=cx−b, we have

(3)

where the final equality is valid because b 2=4ac 2, and hence

$$\chi\bigl[c^2 x^2 - b^2\bigr] = \chi \bigl[c^2\bigl(x^2 - 4a\bigr) \bigr] = \chi \bigl[c^2\bigr] \chi\bigl[x^2 - 4a\bigr] = \chi \bigl[x^2 -4a\bigr].$$

Since (e 2πibn/p)2=e 2πimn/p=(e πimn/p)2, we have e 2πibn/p=±e πimn/p, and therefore by (3) and Lemma 3.2,

$$e^{-\pi i mn/p} A_p(\chi)[m,n] =\pm \frac{1}{p} K[1,a;p]\in{\mathbb{R}}.$$

Finally, because a∈ℤ/pℤ∖{0}, we have \(|K[1,a;p]|\leq2\sqrt{p}\), by Weil’s bound for Kloosterman sums in [35]. Thus, (3) gives \(|A_{p}(\chi)[m,n]| \leq2/\sqrt{p}\), as desired. □

Remark 3.5

In [35], Weil proves his bound for |K[a,b;p]| by first using Lemma 3.3 to rewrite K[a,b;p] as ∑χ[x 2−4a]e 2πix/p and then bounding the new sum. Philosophically, then, it would be more direct not to convert the sum to the form ∑exp(2πi(x+ax −1)/p). Nevertheless, we have applied the transformation in Lemma 3.3 because the latter form of Kloosterman sums is better known than are the details of Weil’s proof.

3.2 Main Bound

We shall need the following technical lemma. It gives an exact formula, in terms of A p (χ), for the ambiguity function of any sequence that is a function of the Legendre symbol χ.

Lemma 3.6

Fix an odd prime p and complex numbers r,s,t∈ℂ. Let χ:ℤ/pℤ→ℂ be the Legendre symbol modulo p, and let U:ℤ/pℤ→ℂ be the function

$$U[k] = \begin{cases}r & \text{if } \chi(k)=1,\\s & \text{if } \chi(k)=-1,\\t & \text{if } k=0.\end{cases} $$

Set R=(r+s)/2, S=(r−s)/2, T=t−R, and ζ p =e 2πi/p. Then

$$A_p(U)[m,n] = |S|^2 A_p(\chi)[m,n] +\frac{1}{p} \bigl(E_1[m,n] + E_2[m,n] \bigr)$$

for all m,n∈ℤ/pℤ∖{0}, where \(E_{1}[m,n] = R\bar{T} + \bar{R}T \zeta_{p}^{mn}\), and

$$E_2[m,n] = \begin{cases}(S\bar{T} + \bar{S} T \zeta_p^{mn})\chi[m]+ (R\bar{S} + \bar{R} S \zeta_p^{mn})\chi[n]\sqrt{p}& \text{if } p\equiv1\ (\mathrm{mod}\ 4),\\(S\bar{T} - \bar{S} T \zeta_p^{mn})\chi[m]- (R\bar{S} + \bar{R} S \zeta_p^{mn})i\chi[n]\sqrt{p}& \text{ if } p\equiv3 \ (\mathrm{mod}\ 4).\end{cases} $$

Proof

For any two functions F,G:ℤ/pℤ→ℂ, write

$$B_p(F,G)[m,n] = \frac{1}{p} \sum _{k\in{\mathbb{Z}}/p{\mathbb{Z}}} F[k+m] \overline{G[k]} e^{-2\pi i kn /p}.$$

Define functions η,δ:ℤ/pℤ→ℂ by

$$\eta[k] = 1 \quad \text{and} \quad \delta[k] = \begin{cases}0 & \text{if } k\neq0,\\1 & \text{if } k = 0.\end{cases}$$

Thus, U=Rη+Sχ+Tδ, and hence

To compute B p (U,U), we shall compute each of these nine terms separately. Since m≠0, we have B p (δ,δ)=0. In addition, B p (η,η)=0, since ∑ k∈ℤ/pℤ e −2πikn/p=0 and n≠0. We also have B p (χ,χ)=A p (χ) by definition. Meanwhile, it is immediate that

Next, pB p (η,χ)[m,n]=τ[−n;p], where τ[a;p] is the Gauss sum

$$\tau[a;p] = \sum_{k\in{\mathbb{Z}}/p{\mathbb{Z}}} \chi[k] e^{2\pi iak /p}.$$

However, Gauss proved that \(\tau[a;p]=\varepsilon\chi[a]\sqrt{p}\), where ε=1 if p≡1(mod 4), and ε=i if p≡3(mod 4); see, for example, Proposition 6.3.1 and Theorem 6.4.1 of [18]. Hence, \(pB_{p}(\eta,\chi)[m,n] = \varepsilon\chi[-n]\sqrt{p}\). Similarly,

Combining the nine computations above, and noting that

$$\chi[-k]=\chi[-1]\chi[k] \begin{cases}\chi[k] & \text{if } p \equiv1\ (\mathrm{mod}\ 4),\\-\chi[k] & \text{if } p \equiv3\ (\mathrm{mod}\ 4),\end{cases} $$

we have B p (U,U)=|S|2 A p (χ)+(E 1+E 2)/p, where E 1 and E 2 are the quantities in the statement of Lemma 3.6. □

The following elementary bound will be needed to prove the p≡3(mod 4) case of Theorem 3.8.

Lemma 3.7

Let X,Y∈ℝ, and let z∈ℂ with |z|=1. Then

$$|zX + \bigl(1-z^2\bigr)Y| \leq\sqrt{X^2 +4Y^2}.$$

Proof

Noting that \(z\overline{z}=1\), we have

since \(z(1-\overline{z}^{2}) + \overline{z}(1-z^{2})= z - \overline{z} + \overline{z} - z = 0\) and |1−z 2|≤2. □

We are now ready to state and prove our main result.

Theorem 3.8

Let p be an odd prime, and let u p be the Björck function for p. Then the ambiguity function, A p (u p ), defined on ℤ/pℤ×ℤ/pℤ as

$$A_p(u_p)[m,n] = \frac{1}{p} \sum _{k\in{\mathbb{Z}}/p{\mathbb{Z}}} u_p[k+m] \overline{u_p[k]}e^{-2\pi i kn/p},$$

satisfies the estimate

$$|A(u_p)[m,n]| < \frac{2}{\sqrt{p}} + \begin{cases}\frac{4}{p} & \text{if } p\equiv1\ (\mathrm{mod}\ 4),\\\frac{4}{p^{3/2}} & \text{if } p\equiv3\ (\mathrm{mod}\ 4),\end{cases} $$

for all (m,n)∈(ℤ/pℤ×ℤ/pℤ)∖{(0,0)}.

Proof

Fix (m,n)∈(ℤ/pℤ×ℤ/pℤ)∖{(0,0)}. If m=0, then n≠0, and we have

$$A_p(u_p)[0,n] = \frac{1}{p}\sum _{k\in{\mathbb{Z}}/p{\mathbb{Z}}} u_p[k] \overline{u_p[k]}e^{-2\pi ik n/p} = \frac{1}{p}\sum_{k\in{\mathbb{Z}}/p{\mathbb{Z}}}e^{-2\pi ik n/p} = 0,$$

since |u p [k]|=1 for all k∈ℤ/pℤ. On the other hand, if n=0, then m≠0, and we have

$$A_p(u_p)[m,0] = \frac{1}{p}\sum _{k\in{\mathbb{Z}}/p{\mathbb{Z}}} u_p[k+m] \overline{u_p[k]} =0,$$

because u p has zero autocorrelation. Thus, by the fact that u p is a CAZAC, we may assume for the remainder of the proof that m,n≠0.

If p≡1(mod 4), then in the notation of Lemma 3.6, we have \(r=(1+\sqrt{p})^{-1}(1 + i \sqrt{2\sqrt{p} + p})\), \(s=(1+\sqrt{p})^{-1}(1 - i \sqrt{2\sqrt{p} + p})\), and t=1. Thus,

The quantities E 1 and E 2 in Lemma 3.6 are therefore

$$E_1[m,n] = \frac{\sqrt{p}(1+\zeta_p^{mn})}{(1+\sqrt{p})^2}$$

and

Noting that \(|1+\zeta_{p}^{mn}|\), \(|1-\zeta_{p}^{mn}|\), and |χ[m]−χ[n]| are each less than or equal to 2 and that \(\sqrt{2\sqrt{p} + p} < \sqrt{1 + 2\sqrt{p} + p} = 1 +\sqrt{p}\), we obtain

$$|E_1[m,n] + E_2[m,n]| < \frac{2\sqrt{p}}{(1+\sqrt{p})^2} +\frac{4\sqrt{p}}{1+\sqrt{p}} < \frac{2\sqrt{p}}{(1+\sqrt{p})^2} + 4.$$

Hence, by Lemma 3.6 and Theorem 3.4, we have

Similarly, if p≡3(mod 4), then r=1, \(s=(1+p)^{-1}(1-p + 2 i \sqrt{p})\), and t=1, and therefore

$$R= \frac{r+s}{2} = \frac{1}{1-i\sqrt{p}}, \qquad S= \frac{r-s}{2} =\frac{-i\sqrt{p}}{1-i\sqrt{p}}, \quad\text{and}\quad T=t-R = \frac{-i\sqrt{p}}{1-i\sqrt{p}}.$$

Thus, the quantities E 1 and E 2 in Lemma 3.6 are

$$E_1[m,n] = \frac{i\sqrt{p}(1-\zeta_p^{mn})}{p+1}$$

and

Since |S|2=p/(p+1), we have

$$| |S|^2 A_p(\chi)[m,n] + \frac{1}{p}E_2[m,n] | = \frac{1}{p+1} |pA_p(\chi)[m,n] +\bigl(1-\zeta_p^{mn}\bigr) \bigl(\chi[m] + \chi[n]\bigr) |.$$

Setting z=e πimn/p, X=e −πimn/p pA p (χ)[m,n], and Y=χ[m]+χ[n], so that X∈ℝ with \(|X|\leq2\sqrt{p}\) by Theorem 3.4, Y∈ℝ with |Y|≤2, and |z|=1, Lemma 3.7 tells us that

$$\bigg| |S|^2 A_p(\chi)[m,n] + \frac{1}{p}E_2[m,n] \bigg| \leq \frac{\sqrt{X^2 + 4Y^2}}{p+1} \leq \frac{\sqrt{4p + 16}}{p+1} =\frac{2\sqrt{p+4}}{p+1}.$$

Hence, by Lemma 3.6 and the fact that \(|1-\zeta_{p}^{mn}|\leq2\), we obtain

 □

Remark 3.9

The bounds in Theorem 3.8 may be improved very slightly but at the great expense of simplicity. For example, if p≡1(mod 4), then the bounds \(|1-\zeta_{p}^{mn}|\leq2\) and \(|1+\zeta_{p}^{mn}|\leq2\) could be improved, as obviously these quantities cannot both be simultaneously close to 2. However, the resulting bound is far more complicated to write, and the savings is only about 2p −3/2, as illustrated by considering \(\zeta_{p}^{mn}\) very close to −1. Similarly, removing the simplification \(4\sqrt{p}/(1+\sqrt{p}) < 4\) would also only save us about 4p −3/2. For further details, including the explicit formula of Lemma 3.6 in the case that U=u p , we refer the reader to [7].

4 Figures and Table

Natural algebraic and analytic calculations convinced us that the proof of Theorem 3.8 depended on substantial number theoretic results. In parallel, Fig. 1 supported the truth of Theorem 3.8 before we proved it. The x-axis lists the primes between 1 and 1000. The y axis lists the values,

$$ \max_{ (m,n) \neq(0,0)}|A_p(u_p)[m,n]|.$$
(4)

Figure 1 also displays the curves \(y=2/\sqrt{p}\) and \(y=2/\sqrt{p} + 4/p\) for comparison. Figure 2, for the case p=13, illustrates the symmetries inherent in the function A p (u p ) on ℤ/pℤ×ℤ/pℤ. These are fully explained for all p in [7]; and they led to the realization of the complexity involved in proving Theorem 3.8, as well as to a host of geometrical and combinatorial phenomena and problems. Figure 3 illustrates Theorem 3.8 for the case p=503.

Fig. 1
figure 1

p and max{|A p (u p )[m,n]|:(m,n)≠(0,0)}

Full size image
Fig. 2
figure 2

A p (u p ) for p=13

Full size image
Fig. 3
figure 3

A p (u p ) for p=503

Full size image

Table 1 indicates some of the finer behavior of the quantity (4), over three different ranges of primes. This data suggested to us that \(2/{\sqrt{p}}\) was very nearly the upper bound for |A p (u p )[m,n]|, (m,n)≠(0,0), and it helped lead us to the proof that \(2/\sqrt{p} + 4/p\) is an upper bound. In addition, although a number of primes p≡1(mod 4) require a bound larger than \(2/\sqrt{p}\), we noted that only very few primes p≡3(mod 4) allowed \(|A_{p}(u_{p})[m,n]|>2/\sqrt{p}\) for (m,n)≠(0,0). For example, p=139 is the only such prime in Table 1. Our broader calculations for other primes showed that the only such primes between 1000 and 5000 are 1259, 2111, and 3511; the only ones between 10000 and 24360 are 13879, 16091 and 23719; and there are none between 100000 and 105000. Moreover, for all seven of those primes, the maximum value of \(|A_{p}(u_{p})[m,n]|-2/\sqrt{p}\) for (m,n)≠(0,0) is still far smaller than 4/p, a fact which ultimately led us to the sharper bound for p≡3(mod 4) in Theorem 3.8.

Table 1 Comparison of max|A p (u p )| outside (0,0) with \(2/\sqrt{p}\)
Full size table