3
$\begingroup$

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.

1 Answers 1

3

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.

  • 0
    @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.2012-04-20