Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a permutation. Is $u$ a polynomial of degree $2$?

Note that the property clearly holds when $u$ is a polynomial of degree $2$. Explicit computations seem to show that the converse holds -- that is, the answer is positive -- for $p$ at most $13$.

This is (in a non-obvious way) a special case of this other question, but presumably the statement here is much easier. The question came up quite naturally when thinking about some aspects of complex Hadamard matrices.

share|improve this question
3  
There must be lots of examples that work for just $l=1,2$: there are $p^p$ functions from ${\bf Z}/p{\bf Z}$ to itself, about $e^{-p}$ of which are permutations; so we expect (very roughly) $e^{-2p} p^p$ random examples, which for large $p$ is way more than the number of quadratic functions. A quick numerical search finds that this first occurs for $p=7$, with $336$ functions of which only $42$ are quadratic. One that isn't has $f(n)=0,0,1,3,0,3,2$ for $n=0,1,2,3,4,5,6$. (But none of them extends to a counterexample for $l=3$, which would refute the conjecture at hand.) –  Noam D. Elkies Jul 7 '13 at 3:15
3  
Off-topic, but sometimes I think the world's fetish for blackboard bold over actual bold has become the catechism of a cult... (This comment directed at the recent edit, not at the original post.) –  Yemon Choi Jul 7 '13 at 5:12
2  
@YemonChoi: your concept of "world" is an interesting one, since most of the denizens of the planet would not know \mathbb if it came up and bit them on the tender parts. –  Igor Rivin Jul 7 '13 at 5:43
1  
If $u$ is a polynomial, then $u(k+l)-u(k)$ will be a polynomial of one lower degree. So one could try to analyze which polynomials give permutations, and see if one of these can arise as such a difference. en.wikipedia.org/wiki/Permutation_polynomial –  Ian Agol Jul 7 '13 at 16:11
1  
I record the following equivalent statement. Suppose that $g\colon \mathbb Z/p\mathbb Z \to \mathbb Z/p\mathbb Z$ is a permutation such that each of the following functions are also permutations: $g(x)+g(x+1)$ and $g(x)+g(x+1)+g(x+2)$ and so on. Must $g$ be a linear polynomial? (The connection is that $g(x) = u(x+1)-u(x)$.) –  Greg Martin Jul 7 '13 at 18:17

2 Answers 2

up vote 36 down vote accepted

Yes, $u$ must be a polynomial of degree $2$. I had to draw on a few unexpected ingredients to prove this; perhaps there's a simpler proof. [EDIT Or maybe not: Peter Mueller's answer reports that this was "an open problem on planar functions for many years", and gives links to three independent papers c.1990 that independently solved it. Two of them give the same argument that I found 23 years later, and the third, by Hiramine, either avoids or re-proves Segre's theorem but is even more complicated.]

Let $\kappa$ be the finite field ${\bf Z}/p{\bf Z}$ (usually this would be called $k$, but that letter's already taken). Fix a nontrivial $p$-th root of unity $\rho \in {\bf C}$, say $\rho = e^{2\pi i/p}$; for any $n \in \kappa$ we shall naturally use $\rho^n$ to mean $\rho^{\tilde n}$ for any lift $\tilde n$ of $n$ to ${\bf Z}$. Let $K$ be the $p$-th cyclotomic field ${\bf Q}[\rho]$, and $A = {\bf Z}[\rho]$ its ring of algebraic integers, which contains the Gauss sum $\gamma := \sum_{n \in \kappa} \rho^{n^2} \in A$, with $\gamma^2 = \pm p$ according as $p \equiv \pm 1 \bmod 4$. For any $p$-th roots of unity $\omega,\zeta \in A$ with $\zeta \neq 1$, define $$ G(\omega,\zeta) = \sum_{k \in \kappa} \omega^k \zeta^{u(k)}. $$ I claim that $G(\omega,\zeta)$ is $\pm\gamma$ times some $p$-th root of unity (as it must be if $u$ is quadratic). We prove this by mimicking the usual proof of $\left|\gamma\right|^2 = p$: write $$ \left|G(\omega,\zeta)\right|^2 = \mathop{\sum\sum}_{k,k' \in \kappa} \omega^{k'-k} \zeta^{u(k')-u(k)} = \sum_{l \in \kappa} \left[ \omega^l \sum_{k \in \kappa} \zeta^{u(k+l)-u(k)} \right] $$ where $l=k'-k$; now for $l=0$ the inner sum is $\sum_k 1 = p$, and for $l\neq 0$ the inner sum vanishes by the hypothesis on $u$ (it is a permutation of $\sum_{n\in\kappa} \zeta^n = 0$), so $\left|G(\omega,\zeta)\right|^2 = p$. This holds for every Galois conjugate of $G(\omega,\zeta)$, so the algebraic norm of $G(\omega,\zeta) \in K$ is $p^{(p-1)/2}$. Because there's a unique prime of $K$ above $p$, it follows that $\gamma^{-1} G(\omega,\zeta)$ is an algebraic integer all of whose Galois conjugates have absolute value $1$. By a theorem of Kronecker this integer must be a root of unity. This proves the claim that $G(\omega,\zeta)$ is of the form $\pm\zeta^s\gamma$, because the only roots of unity in $A$ are powers of $\rho$ and their negatives. [EDIT Gluck's paper (Discrete Math. 80 (1990) 97$-$100) cites Theorem 1 of "Cavior, S.: Exponential sums related to polynomials over GF(p), Proc. A.M.S. 15 (1964) 175$-$178" for the result that $\pm\zeta^s\gamma$ are the only elements of absolute value $\sqrt p$ in $A$.]

Now for any $c \in \kappa$ we have $G(\rho^c,\rho) = \sum_{k \in \kappa} \rho^{u(k)+ck}$, which is a representation of some $\pm\rho^a\gamma$ as a sum of $p$ powers of $\rho$. This representation is unique because the cyclotomic polynomial $\sum_{n=0}^{p-1} X^n$ is irreducible and does not vanish at $X=1$. We already know one such representation, $\pm\rho^s\gamma = \sum_{n\in\kappa} \rho^{an^2+s}$, where $a$ is a quadratic residue or nonresidue of $p$ according to the choice of plus or minus sign. Therefore $u(k)+ck$ must take the same values and multiplicities as $an^2+s$ when $k$ varies over $\kappa$. In particular each $b \in {\bf Z}/p{\bf Z}$ occurs at most twice as $u(k)+ck$. (Could this conclusion have been reached without the foray into algebraic number theory?)

This strongly suggests that $u$ must be quadratic, but the implication is still not obvious. To reach that conclusion we use a theorem of Segre on ovals in algebraic projective planes of odd order. Recall that an oval in a projective plane $\Pi$ of order $q$ is a $(q+1)$-element set of points of $\Pi$ that meets each line in at most $2$ points. For example, a conic in an algebraic projective plane is an oval.

Theorem (Segre 1955). If $F$ is a finite field of odd order then every oval in ${\bf P}^2(F)$ is a conic.

Now we have just proved that the subset $\lbrace (x,y) = (k,u(k)) : k \in \kappa \rbrace$ of the affine plane $\kappa^2$ meets every line $cx+y=b$ in at most two points; it also meets every line $x=x_0$ in exactly one point. Thus we can construct an oval ${\cal O}$ in ${\bf P}^2(\kappa)$ consisting of these points $(k:u(k):1)$ together with the point at infinity $(0:1:0)$. By Segre's theorem $\cal O$ is a conic. Since it meets the line at infinity at just the one point $(0:1:0)$, this conic ${\cal O}$ consists of that point together with the graph of a quadratic polynomial, QED.

share|improve this answer
1  
Noam D. Elkies: thanks! It's a very nice proof, which I'll need some time to fully digest. And a good motivation to learn some number theory. (Incidentally, should the reference to Schur's theorem in the last sentence be to Segre's theorem?) –  Jean-Marc Schlenker Jul 8 '13 at 8:59
    
Thanks! And yes, Segre, not Schur; I just fixed it. (Thanks also to Olivier for correcting my TeXo [missing backslash in "\in"]). –  Noam D. Elkies Jul 8 '13 at 11:07
1  
... and thanks to GH from MO for correcting two further typos. –  Noam D. Elkies Jul 13 '13 at 19:15
    
You are welcome! –  GH from MO Jul 29 '13 at 21:08

The question was an open problem on planar functions for many years, which was settled independently in three papers around 1990. See the papers by Gluck, Ronyai and Szonyi, and Hiramine. Elkies' answer is similar to Gluck's proof. The proof by Hiramine avoids Segre's theorem, it is based on quite complicated computations instead.

share|improve this answer
    
Peter Mueller: thanks for those references! I had no idea the question was ever considered in this area of mathematics. –  Jean-Marc Schlenker Jul 9 '13 at 19:54
6  
Actually, your question makes sense over any finite field, and presently many preprints and papers are being produced. The point is that if the field has not prime order, many more examples beyond the quadratic ones exist. By the way, the finite geometers call these functions planar, while the cryptography people call them perfect nonlinear. As far as I know, it took some time until these two communities realized that they study the same objects, for quite different reasons though. –  Peter Mueller Jul 10 '13 at 9:33
1  
Thanks for this comment. It might be useful. But actually in the applications we have in mind, there is a "natural" generalization where $p$ is not prime, but it's not in terms of fields and permutations any longer, so it probably goes in a different direction than the one considered when looking at this in terms of finite fields. Anyway, I'll have a look. –  Jean-Marc Schlenker Jul 13 '13 at 16:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.