5
$\begingroup$

Fix a finite set of integers $S$ and a prime number $p$. Let $(a_1, a_2, \dotsc, a_n)$, $(b_1, b_2, b_3, \dotsc, b_n)$ be two sequences of integers where the numbers $a_i$ and $b_i$ are chosen uniformly from the set $S$ (In the case I care about S = {-2,-1,1,2 }). I would like to understand what is the probability that $$\sum_{i_1 < i_2 < \dotsb < i_k } a_{i_1}a_{i_2}\dots a_{i_k} = 0 \mod p$$ an the probability that $$\sum_{i_1 \leq j_1 < i_2 \leq j_2 < \dotsb < i_k \leq j_k} a_{i_1}b_{j_1}\dots a_{j_k}b_{j_k} = 0 \mod p.$$

I am interested in the asymptotic probabilities as $n$ increases and $k$ is fixed (or $k$ grows much slower than $n$) and expect some type of equidistribution as $n$. One particular case is Question about estimating random symmetric sums modulo p, where one particular sum is reduced to the linear case. Can this trick be for the general case?

Any suggestion, trick or vaguely related information related to this is highly appreciated.

P.S. Can the second type of sum (the one involving $a_i$, $b_i$) be somehow related to a sum of the first type?, the ordering makes things much more tricky and I am wondering whether there is a procedure to reduce this sum to the first type. (Also the second sum even though not so natural is the one that I really need to understand).

Thanks!

$\endgroup$
1
  • $\begingroup$ Have you done any computations for small $p$ and $n$? $\endgroup$
    – kodlu
    Aug 19 at 8:57
7
$\begingroup$

Using the Newton identities, one can (in the high characteristic regime $p>k$) express the elementary symmetric polynomial $\sum_{i_1 < \dots < i_k} a_{i_1} \dots a_{i_k}$ in terms of the moments $\sum_{i=1}^k a_i^j$ for $j=1,\dots,k$. The question then boils down to the equidistribution of $\sum_{i=1}^k (a_i^j)_{j=1}^k$ in ${\mathbf F}_p^k$. There is however an obstruction to equidistribution because the points $(a^j)_{j=1}^k$ for $a=-2,-1,1,2$ do not span the entirety of ${\mathbf F}_p^k$ once $k \geq 4$, due to the existence of non-trivial polynomials $P$ of degree $4$ or higher that vanish at $-2,-1,1,2$. For instance because $P(x) = (x+2)(x+1)(x-1)(x-2) = x^4 - 5 x^2 + 4$ vanishes at these points, the vector $(m_j)_{j=1}^k := \sum_{i=1}^k (a_i^j)_{j=1}^k$ is surely constrained to the hyperplane $m_4 - 5 m_2 + 4k = 0$. This is going to create some distortions to the probability that $\sum_{i_1 < \dots < i_k} a_{i_1} \dots a_{i_k}$ vanishes mod $p$ that can be explicitly calculated for each $p,k$, but the formula is going to be messy (these errors will be of lower order in the limit $p \to \infty$ holding $k$ fixed though, by the Lang-Weil estimates).

(To put it another way, one can use the Newton identities to express the elementary symmetric polynomial as some polynoimal combination of the frequencies $d_{-2}, d_{-1}, d_1, d_2$ that count how often the random sequence $a_1,\dots,a_k$ attains each of its permitted values $-2, -1, 1, 2$. To count the probability that this polynomial vanishes mod $p$, one has to count the points in some variety over ${\bf F}_p$ which in general is a task for the Lang-Weil estimate.)

Your second sum seems to be expressible in terms of a symmetric polynomial in a suitable matrix algebra. If one had $i_k < j_k$ in place of the constraint $i_k \leq j_k$ then one just needs to take the order $2k$ elementary symmetric polynomial of the matrices $\begin{pmatrix} 0 & b_i \\ a_i & 0 \end{pmatrix}$ and extract the top left coefficient. With $i_k \leq j_k$ the situation is more complicated but I expect there is still some sort of matrix representation. However being non-abelian I doubt there is a reduction to the abelian elementary symmetric polynomial considered earlier, and given how complicated that formula already was I'm afraid it is not going to be fun to try to control this sum (except possibly in the asymptotic regime where $p$ is somewhat large and $k$ goes to infinity; actually the nonabelian case might be substantially more "mixing" than the abelian one and one could conceivably get better asymptotics by using some of the theory of expansion of Cayley graphs, but this looks like a lot of work...).

$\endgroup$
3
  • 3
    $\begingroup$ Instead of the Newton identities, a different approach is to observe that the coefficient of $x^k$ in the polynomial $(1-2x)^{d_{-2}} (1-x)^{d_{-1}} (1+x)^{d_1} (1+2x)^{d_2}$ is the $k$th elementary symmetric polynomial in the $a_i$. Expanding this out using the binomial theorem lets us write this as an explicit polynomial in the $d_i$, in particular as a sum of products of binomial coefficients. $\endgroup$
    – Will Sawin
    Aug 20 at 3:48
  • 1
    $\begingroup$ This formulation might be helpful in checking that the obtained polynomial in $d_{-2}, d_{-1}, d_1, d_2$ is actually geometrically irreducible, which seems to be the main difficulty in applying the Lang-Weil estimates (depending on what precision in the answer is needed, of course). $\endgroup$
    – Will Sawin
    Aug 20 at 3:50
  • $\begingroup$ Dear @TerryTao, Thanks a lot for your answer. About the second type of sum, the sums come from a matrix representation as you suggested. It comes from studying the product of matrices $\prod_{i=1}^n \begin{bmatrix} 1 & a_iz\\ 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 0\\ b_iz & 1\end{bmatrix}$ where $z$ is a variable. The sums appear as coefficients of the polynomials given by the entries (in terms of $z$) and I am interested in the first non-zero coefficients of these polynomials. My hope was that these sums were going to be easier to understand than the matrices, but now it looks unlikely. $\endgroup$
    – shurtados
    Aug 20 at 7:05
4
$\begingroup$

Let $F(x_1,\dots,x_n)$ be a polynomial with integer coefficients. Let $p$ be any positive integer. Let $S$ be a finite subset of $\mathbb{Z}$. Then the number of $n$-tuples $(a_1,\dots,a_n)\in S^n$ for which $F(a_1,\dots,a_n) \equiv 0\, (\mathrm{mod}\,p)$ is given by $$ \frac 1p\sum_\zeta \sum_{(a_1,\dots,a_n)\in S^n} \zeta^{F(a_1,\dots,a_n)}. $$ where $\zeta$ runs over all (complex) $p$th roots of 1. The "main term" corresponds to $\zeta=1$.

Perhaps it is possible to use this formula to obtain some estimates, but this doesn't look easy.

$\endgroup$
3
  • $\begingroup$ Dear @RichardStanley, thanks a lot for your answer. I think there seems to be some mistake in the formulas you are giving me (Is there a product instead of sum?, did you mean a pth root of unity?) because for example for $F = x_1$ and $S= \{1, p\}$, the answer should be $2^{n-1}$ and your formula gives something else. Also the asymptotics of the last formula are of the order of $n^k/(p4^n)$ and are not converging to 1/p (which they do for the linear case at least). $\endgroup$
    – shurtados
    Aug 19 at 20:21
  • $\begingroup$ Also @RichardStanley, have you seen sums of the last type (the ones involving $a_i, b_j$ alternating order) somewhere in the literature?, anything where this type of sums appear I am very interested in. $\endgroup$
    – shurtados
    Aug 19 at 20:25
  • $\begingroup$ @shurtados: you are right, my formula was completely wrong. I have replaced it by a correct (I hope) version, but it doesn't look easy to deal with. It could be worthless for your purposes. $\endgroup$ Aug 19 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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