18
$\begingroup$

This is a somewhat more explicit version of a question I have recently asked.

Let $p$ be an odd prime, and write $\zeta:=\exp(2\pi i/p)$ (any other primitive $p$th root of unity will do as well). For integer $n\in[0,p]$, the products $$ {\mathcal P}_p(n) := \prod_{\substack{A\subseteq{\mathbb F}_p \\ |A|=n}}\ \sum_{a\in A} \zeta^a $$ are rational integers; can they be found "explicitly"?

It is immediately seen that ${\mathcal P}_p(0)=0$ and ${\mathcal P}_p(1)=1$, and I can show that ${\mathcal P}_p(2)=\left(\frac2p\right)$ (it is not difficult to see that ${\mathcal P}_p(2)=\pm 1$, but to determine the sign is trickier). Also, we have ${\mathcal P}_p(p-n)=(-1)^{\binom{p}{n}}{\mathcal P}_p(n)$, so that ${\mathcal P}_p(p)=0$, ${\mathcal P}_p(p-1)=-1$, and ${\mathcal P}_p(p-2)=\pm 1$.

$\quad$ What are the values of ${\mathcal P}_p(n)$ for $n\in[3,p-3]$?

Some numerical data (thanks to Talmon Silver for the programming):

$\quad {\mathcal P}_5(3)=-1$
$\quad {\mathcal P}_7(3)=-2^7$
$\quad {\mathcal P}_{11}(3)=23^{11}$
$\quad {\mathcal P}_{13}(3)=159^{13}$
$\quad {\mathcal P}_{17}(3)=-24617^{17}$
$\quad {\mathcal P}_{19}(3)=-611009^{19}$
$\quad {\mathcal P}_{23}(3)=1265401351^{23}$

$\quad$ If finding the individual values ${\mathcal P}_p(n)$ is difficult, can we at least find explicitly the product $$ {\mathcal P}_p(1){\mathcal P}_p(2)\dotsb{\mathcal P}_p(p-2){\mathcal P}_p(p-1) = \prod_{\varnothing\ne A\subsetneq{\mathbb F}_p} \sum_{a\in A} \zeta^a \ ?$$

Denoting this product by ${\mathcal P}_p$,

$\quad {\mathcal P}_3=-1$
$\quad {\mathcal P}_5=-1$
$\quad {\mathcal P}_7=-2^{14}$
$\quad {\mathcal P}_{11}=-(3\cdot 23^4 \cdot 67\cdot 89)^{22}$
$\quad {\mathcal P}_{13}=-(3^{12}\cdot 5\cdot 53^6 \cdot 79^4\cdot 131^2 \cdot 157^2 \cdot 313\cdot 547\cdot 599\cdot 911)^{26}$


The problem can be restated in a purely combinatorial way, as hinted to in Ofir's comment below. Write $N:=\binom pn$, let $A_1,\dotsc,A_N$ be all the $n$-element subsets of ${\mathbb F}_p$, and for $z\in{\mathbb F}_p$ denote by $r_n(z)$ the number of representations $z=a_1+\dotsb+ a_N$ with $a_1\in A_1,\dotsc, a_N\in A_N$. We have then ${\mathcal P}_p(n)=\sum_{z\in{\mathbb F}_p}r_n(z)\zeta^z$, and from the fact that ${\mathcal P}_p(n)$ is an integer, it follows that $r_n(z)$ are actually equal to each other for all $z\in{\mathbb F}_p\setminus\{0\}$; as a result, we have, say, ${\mathcal P}_p(n)=r_n(0)-r_n(1)$. On the other hand, $$ r_n(0)+(p-1)r_n(1) = \sum_{z\in{\mathbb F}_p} r_n(z) = |A_1|\dotsb|A_N| = n^{\binom pn}. $$ This yields $$ {\mathcal P}_p(n) = \frac1{p-1} \left( p\,r_n(0)-n^{\binom pn}\right). $$ Thus, the problem boils down to finding $r_n(0)$, the number of all zero-sum $N$-tuples $(a_1,\dotsc,a_N)$ with the components $a_i$ representing each of the $n$-element subsets of ${\mathbb F}_p$.

$\endgroup$
  • 3
    $\begingroup$ Two observations: 1. This is, in a way, the "dual" of the coefficients of $x^p-1 = \prod_{a=0}^{p-1} (x- \zeta^a)$, which are (up to sign) $\sum_{ A\subseteq \mathbb{F}_{p}, |A|=n} \prod_{a \in A} \zeta ^a$. 2. The case $n=1$ is related to $N(\zeta)=1$, the case $n=2$ to $N(1+\zeta) = 1$ (for $p \neq 2$). The case $n=-3$ is related to $N((1+\zeta)^p+1)$, which is computable mod $p$ as 1. $\endgroup$ – Ofir Gorodetsky Jan 23 '15 at 15:01
  • 2
    $\begingroup$ Up to sign, they appear to be powers of primes, at least for p, n small. I notice $2^7$, $3^8$, $11^{10}$, and $19^9$ cropping up. In particular, $\mathcal{P}_p(n)$ appears to be zero or of the form $\pm q^p$ for $q$ apparently prime (or unity). $\endgroup$ – Steve Huntsman Jan 23 '15 at 16:13
  • 1
    $\begingroup$ I can calculate ${\mathcal P}_p(n) \mod p$ (it's usually 1). Let $A_{1}, \cdots, A_{\binom{p}{n}}$ be the subsets of $\mathbb{F}_{p}$ of size $n$. If we let $X_i$ denote number of solutions to $a_1 + \cdots + a_{\binom{p}{n}} = i \mod p$ for $a_j \in A_j$, we see that ${\mathcal P}_p(n) = \sum_{i=0}^{p-1} X_i \zeta^i$. Since this must be an integer, $X_i$ is constant for $i \neq 0$, and we find ${\mathcal P}_p(n) = X_0 - X_1$. On the other hand, $n^{\binom{p}{n}} = \sum X_i = X_0 + (p-1)X_1 \equiv X_0 - X_1 \mod p$, hence ${\mathcal P}_p(n)\equiv n^{\binom{p}{n}} \mod p$. $\endgroup$ – Ofir Gorodetsky Jan 23 '15 at 18:10
  • 4
    $\begingroup$ @SteveHuntsman I can explain the $p$'th power phenomena. Let $X=\sum_{a \in A} \zeta^a$ be one of the sums appearing in the product. Let $X_{\Delta} = \sum_{a \in A} \zeta^{a+\Delta} = \zeta^{\Delta} X$ be another sum appearing in the product and corresponding to $A+\Delta$. The sums $\{ X+\Delta\}_{\Delta=0}^{p-1}$ are distinct (assuming $0<n<p$), and their product is a $p$'th power of an element of $\mathbb{Z}[\zeta]$, as $\prod_{\Delta=0}^{p-1} X_{\Delta} = X_{\Delta}^{p} \zeta^{\binom{p}{2}} = X_{\Delta}^{p}$. $\endgroup$ – Ofir Gorodetsky Jan 23 '15 at 18:41
  • 1
    $\begingroup$ (cont.) Hence, $\mathcal{P}_{p}(n)^{p-1} = N(\mathcal{P}_{p}(n)) = N(a^p) = N(a)^p$ for some $a \in \mathbb{Z}[\zeta]$. As $N(a)$ is an integer, we find $\mathcal{P}_{p}(n)$ is a $p$'th power. $\endgroup$ – Ofir Gorodetsky Jan 23 '15 at 18:44
2
$\begingroup$

Only a partial answer:

I can prove that ${\cal P}_p(3)=\epsilon_p v_p^p$, with $\varepsilon_p^2=1$, for every integer $p\ge 3$ (not necessarily prime). The proof is too technical to present here. The values of $v_p$ are given by $$ v_p^6=\frac{9W_p}{(2^p-(-1)^p)^2(1-(-2)^p)}, $$ where $$ W_p=\prod_\zeta\{(1+\zeta)^p-(-1)^p\}; $$ except for the sign these $W_p$ are the numbers of sequence A096964 in OEIS (Wendt's determinant).

Also $W_p=\det(M+(1-(-1)^p) I)$ where $M$ is the circulant matrix with first line $\binom{p}{k}$ for $0\le k\le p-1$.

The sequence $\varepsilon_p$ appear to have a simple periodic structure, but this I have not proved.

$\endgroup$
  • $\begingroup$ @Seva My formulas are valid for any natural number $p\ge3$. $\endgroup$ – juan Jan 29 '15 at 22:04

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.