# Discrete log of consecutive numbers

I am trying to understand the relation of additive and multiplicative structure of finite field of prime cardinality.

Let's say I have a set that behaves nice additively - an interval $I = \{a,a+1,\cdots ,b\} \subseteq \mathbb{F}_{p}$. I allow the size $b-a$ to be quite large - $\Omega(p)$.

What can be said about its multiplicative structure, i.e. of the discrete log of the elements (with respect to some generator)? Specifically, I am interested in the behavior of the multiset $\{(\log(a) - \log(a')) \mod p-1 | a,a' \in I \}$. Simulations show that each non-zero value appears about $|I|^2 / (p-2)$ times, as expected. Can this be proved rigorously?

I feel that this question is related to the Polya-Vinogradov inequality, which states that the sum of a character over consecutive integers behaves like a Bin(n,0.5).

EDIT (correction and a direction): It may happen for some intervals $I$ that some non-zero values modulo $p-1$ appear much less\more than expected (but the set of these values is rather small). Because of this, it seems that an average result is more fitting in this situation (instead of an absolute result).

Namely, if we let $f(x) = |I \cap Ix|$ to be the function counting the times $\log_g(x)$ appears in our multiset, then Average$(f) = \frac{1}{p-1}\sum_{x=1}^{p-1} f(x) = \frac{|I|^2}{p-1}$. From simulations, Variance$(f) = \frac{1}{p-1} \sum_{x=1}^{p-1} (f(x)-$Average$(f))^2$ is small - about $\frac{|I|^2}{p-2}$.

Writing $|Ix \cap I|$ as $\sum_{b_1, b_2 \in I} 1_{x b_1 = b_2}$, we get: $$\frac{1}{p-1} \sum_{x=1}^{p-1} |Ix \cap I|^2 = \frac{1}{p-1} \sum_{x=1}^{p-1} \sum_{b_1,b_2,b_3,b_4 \in I} 1_{x = \frac{b_2}{b_1} = \frac{b_4}{b_3}} =\frac{1}{p-1} \sum_{b_1,b_2,b_3,b_4 \in I} 1_{b_2 b_3 / b_1 b_4 = 1} =$$ and by using orthogonality relations of characters (similar to Jyrki's post), it simplifies to: $$= \frac{1}{(p-1)^2} \sum_{\chi } \sum_{b_1, b_2, b_3, b_4 \in I} \chi(b_2 b_3 b_1^{-1} b_4^{-1})=\frac{1}{(p-1)^2} \sum_{\chi } |\sum_{b \in I} \chi(b)|^4$$

The term corresponding to $\chi = 1$ equals $\frac{|I|^4}{(p-1)^2}$ and it cancels Average$(f)^2$, so the variance is:

$$\frac{1}{(p-1)^2} \sum_{\chi \neq 1} |\sum_{b \in I} \chi(b)|^4$$

which is an elegant expression, but why is it small? The Polya-Vinogradov gives the upper bound $O(p \log^4 p)$, but I think the $\log$ term can be made smaller.

-

It seems to me that your multiset is, indeed, closely related to Polya-Vinogradov. This is only worth a comment, hence CW, but I want to get started on this. Undoubtedly you reached (at least) the same point.

Let $g$ be a primitive element (= basis of your discrete log). For all $\ell=0,1,\ldots,p-2$, let $\chi_\ell$ be the Dirichlet character $\chi_\ell(a)=\zeta_{p-1}^{\ell\cdot \log a}$, where $\zeta_{p-1}=e^{2\pi i/(p-1)}$ is the obvious root of unity.

We have the usual relation $$\sum_{\ell=0}^{p-2}\chi_\ell(x)=\left\{ \begin{array}{ll} p-1,&\text{if}\ x=1,\\ 0,&\text{if}\ x\neq0,1. \end{array}\right.$$

The equation $\log a -\log a'\equiv t\pmod{p-1}$ is equivalent to $a=a'g^t$, so (given that $a\neq0\neq a'$). Let us define for $t\not\equiv0$ $$N(t)=|\{(a,a')\in I^2\mid \log a-\log a'\equiv t\}.$$ Then putting these pieces together we get \begin{aligned} N(t)&=\frac1{p-1}\sum_{\ell=0}^{p-2}\sum_{a\in I}\sum_{a'\in I}\chi_\ell(aa'^{-1}g^{-t})\\ &=\frac1{p-1}\sum_{\ell=0}^{p-2}\chi_\ell(g^{-t})\sum_{a,a'\in I}\chi_\ell(a/a')\\ &=\frac1{p-1}\sum_{\ell=0}^{p-2}\chi_\ell(g^{-t})\left\vert\sum_{a\in I}\chi_\ell(a)\right\vert^2. \end{aligned} Separating the term with $\ell=0$, when the sum inside absolute values is $|I|$, we end up with $$N(t)=\frac1{p-1}\left(|I|^2+\sum_{\ell=1}^{p-2}\chi_\ell(g^{-t})\left\vert\sum_{a\in I}\chi_\ell(a)\right\vert^2\right),$$ and the inner sums are of the Polya-Vinogradov type.

Here it is tempting to conjecture that the first term dominates. Unfortunately the Polya-Vinogradov inequality (together with the triangle inequality) is not strong enough to say that. We need something stronger to prove that in the last sum some cancellation will take place. This is to be expected as the oscillating terms $\chi_\ell(g^{-t})$ are multiplied by positive real numbers. I need to think more about this.

-
Very nice progress. I actually didn't arrive at this expression, I should have thought of using orthogonality relations as wisely as you did. Maybe the original proof of Polya-Vinogradov can be modified to suite our case. –  Ofir Apr 20 '12 at 14:55
I think I might have to add additional constraints. It seems that for some values of $t$, $N(t)$ is smaller\larger than expected. For example, if $B$ is close to the interval $[p/3, 2p/3]$ then $N(2)$ is very small. I will do some simulations and post an update. –  Ofir Apr 20 '12 at 15:11
@Ofir. Yeah, I'm also thinking that a calculation along the Polya-Vinogradov technique may do the trick. IIRC for another similar kind of a linear combination of sums restricted to an interval a surprisingly good bound came out. –  Jyrki Lahtonen Apr 20 '12 at 15:23