Polymath proposal: explaining identities for irreducible polynomials

December 28, 2015

Polymath proposal: explaining identities for irreducible polynomials

Filed under: planning,polymath proposals — Terence Tao @ 7:05 pm

I am posting this proposal on behalf of Dinesh Thakur.

Let $F_2[t]$ be the ring of polynomials over the finite field $F_2$ of two elements, and let

$\displaystyle {\mathcal P} = \{t, t+1, t^2+t+1, \dots \}$

be the set of irreducible polynomials in this ring. Then infinite series such as

$\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P} = \frac{1}{t+1} + \frac{1}{t} + \frac{1}{t^2+t} + \dots$

and

$\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P^3} = \frac{1}{t^3+1} + \frac{1}{(t+1)^3+1} + \frac{1}{(t^2+t+1)^3+1} + \dots$

can be expanded as formal infinite power series in the variable $t = 1/u$ .

It was numerically observed in http://arxiv.org/abs/1512.02685 that one appears to have the remarkable cancellation

$\displaystyle{}\sum_{P \in {\mathcal P}} \frac{1}{1+P} = 0$

and

$\displaystyle{}\sum_{P\in{\mathcal P}} \frac{1}{1+P^3}=\frac{1}{t^4+t^2}$

$\displaystyle = u^4 + u^6 + u^8 + \dots.$

For instance, one has

$\displaystyle \frac{1}{t+1} = u + u^2 + u^3 + \dots$

$\displaystyle \frac{1}{t} = u$

$\displaystyle \frac{1}{t^2+t} = u^2 + u^3 + \dots$

and all other terms in $\sum_{P \in {\mathcal P}} \frac{1}{1+P}$ are of order $u^3$ or higher, so this shows that ${}\sum_{P \in {\mathcal P}} \frac{1}{1+P}$ has $u$ -valuation at least 3. Similarly, if one expands the first sum for all primes of degree (in $t$ ) up to 37, one obtains ${}u^{38}+u^{39}+u^{44}+u^{45}+\dots$ (the calculation took about a month on one computer), implying that the $u$ -valuation of the infinite sum is at least 38; in fact a bit of theory can improve this to 42. (But we do not know whether this 42 is the answer to everything!).

For the second sum, calculation for degrees up to 28 shows that the difference between the two sides has $u$ -valuation at least 88.

The polymath proposal is to investigate this phenomenon further (perhaps by more extensive numerical calculations) and supply a theoretical explanation for it.

Background links:

The paper http://arxiv.org/abs/1512.02685 where these (and many more guesses of this type) are given with some background on zeta deformation etc, and
http://www.math.rochester.edu/people/faculty/dthakur2/primesymmetryrev.pdf where the updated version is and will be maintained.

Below the fold is some more technical information regarding the above calculations.

To show how complicated the cancellations are we record triples with degree $d$ , then $u$ -power for the first sum for degree $d$ primes followed by the $u$ -valuation

for the first sum for degrees up to $d$ .

$(1,2,2), (2,2,\infty), (3,4,4), (4,4,8), (5,6,6), (6,6,8), (7,8,10), (8,18,10),$

$(9,12,10),(10,10,14),(11,12,12),(12,12,16),(13,14,14),(15,16,18),$

$(16,34,18),(17,18,22),(18,26,22),(19,20,20), (20,20,28),(21,22,22),$

$(22,22,24),(23,24,26),(24,34,26),(25,30,26),(26,26,28),(27,36,28),$

$(28,28,32),(29,30,30),(30,30,32),(31,32,36),(32,66,36),(33,34,34),$

$(34,34,36), (35, 36, 40), (36, ?, 40), (37, 38, 38)$

Since the computation was done to precision $46$ , we only know that for degree $=36$ the sum had $u$ -valuation at least $46$ , but do not know precise value. (I would like to know!).

Remarks: It might be best for the first sum to calculate to precision about $u^{50}$ (ignoring $u^{51}$ and more) and second about $u^{100}$ . (The valuations are even, so e.g., $u^{49}$ or $u^{51}$ will be waste.). Rather than making a full list (huge) and then summing, it is better to calculate both sums term by term (simultaneously) as the P’s are produced.

Probably different range of polynomials can be checked for irreducibility and sum calculated for it on different computers and then combined at the end. Simplest calculation will be degree 38 calculation for the first sum to precision $u^{44}$ (since the earlier calculation had this precision). (To go beyond $38$ , I suggest $50$ , as you cannot improve it later). There are many more sums for different $q=2^n$ ‘s and powers $k$ ‘s. I have written up some answers in the links above, any of which can be checked independently.

Comments (63)

63 Comments »

[…] on the polymath blog, I’ve posted (on behalf of Dinesh Thakur) a new polymath proposal, which is to explain some numerically observed identities involving the irreducible polynomials in […]

Pingback by A new polymath proposal: explaining identities for irreducible polynomials | What's new — December 28, 2015 @ 7:40 pm | Reply
What happens for other characteristics?

Comment by Joshua Zelinsky — December 28, 2015 @ 10:56 pm | Reply
What’s the fastest way to find irreducible polynomials over F_2? Presumably there’s something smarter than the sieve of Eratosthenes…?

Comment by Dustin G. Mixon — December 28, 2015 @ 11:43 pm | Reply
- Just factor $T^{2^d}-T$ using Berlekamp’s algorithm.
  
  Comment by Ofir Gorodetsky — December 29, 2015 @ 5:26 am | Reply
- As mentioned above, it’s not clear that this is the best method for reasons of space. Enumerating polynomials one at a time takes space O(d), whereas to write down the full factorization of t^(2^d)-t will require something more like O(2^d) space. It would be better to have a fast irreducibility = primality test.
  
  Comment by John Voight — December 29, 2015 @ 8:57 pm | Reply
  - I believe the fastest way to find irreducible polynomials, factor, or do modular composition over F_2 would be in the recent Kedlaya-Umans work: http://users.cms.caltech.edu/~umans/papers/KU08-final.pdf
    
    This might lend itself to some additional efficiencies over and above finding the irreducible polynomials.
    
    Comment by John Nicol — December 30, 2015 @ 12:59 am | Reply
I believe I understand why the three lines of TeX which do not currently parse are not currently parsing. There are additional spaces in the TeX (which of course compile perfectly fine in LaTeX but which the WordPress Plugin cannot handle). For one particular example, I believe there is an additional space after the comma after the first paren-group (9, 12, 10) in the first formula which does not compile. [Please forgive me if I’m wrong — there is some guesswork as I don’t see the actual source].

[That seemed to fix the parsing errors for those three lines, though I’m still having trouble getting some other LaTeX code to parse at all. Will keep trying – T.]

Comment by David Lowry-Duda — December 29, 2015 @ 4:20 am | Reply
I intend to check later the following sum – sum_(P monic irreducible in F_q[T]) 1/(1-P^(q-1)). The summand can also be written as sum(a in F_q*) 1/(1-aP), which generalizes the F2 case (but might be completely wrong generalization…). I’ll have time only a day from now, so if someone wants to do it, that would be great.

Comment by Ofir Gorodetsky — December 29, 2015 @ 5:33 am | Reply
- https://s0.wp.com/latex.php?latex=%28%5Csum_%7BP+%5Cin+%7B%5Cmathcal+P%7D%3A+%5Chbox%7Bdeg%7D%28P%29+%5Chbox%7B+odd%7D%7D+%5Cfrac%7B1%7D%7B1%2BP%7D%29+%28%5Csum_%7BQ+%5Cin+F_2%5Bt%5D%3A+Q+%5Cneq+0%7D+%5Cfrac%7B1%7D%7BQ%7D%29+%3D+%5Csum_%7BQ+%5Cin+F_2%5Bt%5D%3A+Q+%5Cneq+0%2C+%5Chbox%7Bdeg%7D%28Q%29+%5Chbox%7B+odd%7D%7D+%5Cfrac%7B1%7D%7BQ%7D&bg=ffffff&fg=000000&s=0
  
  Comment by sdsd — January 21, 2019 @ 12:45 pm | Reply
This doesn’t seem to directly help much with the original problem, but there is the identity

$(\sum_{P \in {\mathcal P}: \hbox{deg}(P) \hbox{ odd}} \frac{1}{1+P}) (\sum_{Q \in F_2[t]: Q \neq 0} \frac{1}{Q}) = \sum_{Q \in F_2[t]: Q \neq 0, \hbox{deg}(Q) \hbox{ odd}} \frac{1}{Q}$

arising from the fact that the number of odd-degree irreducible polynomials $P$ dividing a given non-zero polynomial $Q$ (counting multiplicity) will have the same parity as the degree of that polynomial, thanks to the fundamental theorem of arithmetic in $F_2[t]$ . In principle this should let one compute the odd-degree component of $\sum_{P \in {\mathcal P}} \frac{1}{1+P}$ . I don’t know how to deal with the even-degree component though.

Comment by Terence Tao — December 29, 2015 @ 5:35 am | Reply
This looks like a very nice project! If turned into a full project this will be (I think) the first time that we have more than one polymath project running in parallel and this is very welcomed! Right now polymath10 devoted to the Erdos-Rado sunflower conjecture is running in my blog; Here is the link to the first post. It is possible that yet another polymath project will take place over a third blog in the coming months.

Comment by Gil Kalai — December 29, 2015 @ 6:00 am | Reply
This seems like a nice project. It also seems amenable to some early direct computation, which I think has served past polymath projects well.

I wonder if there is a nice way to parallelize construction of irreducible polynomials up to degree d. Or more simply, is there a good way to construct irreducible polynomials of degree d+1 without constructing irreducible polynomials of degree d? One conceivable answer might be to run Berlekamp’s Algorithm (as mentioned by Ofir above) on $(T^{2^{d+1}} - T)/(T^{2^d} - T)$ . I do not know the implementation or running time of Berlekamp’s Algorithm to know whether or not this would save time or merely add to it.

Comment by David Lowry-Duda — December 29, 2015 @ 6:58 am | Reply
The triple for d=14 is missing. Judging by d=13 and 15, it ought to be (14,14,16).

Comment by Dustin G. Mixon — December 29, 2015 @ 11:30 am | Reply
- Yes, the missing triple is (14,14,16).
  
  Comment by John Voight — December 29, 2015 @ 8:53 pm | Reply
I vaguely remember that there are some nice formulas and nice related combinatorics for the product of all irreducible polynomials of a given degree (namely you can derive it by either using a little more Galois theory, or a little more generating functions machinery).

Comment by Gil Kalai — December 29, 2015 @ 6:42 pm | Reply
- Gil, you remember correctly. If you denote by P_n the product of the monic irreducibles of degree n in F_q[T], then the product of P_d over d dividing n is T^(q^n)-T (consequence of F_(q^n) being a field containing exactly the roots of all these polynomials, and of Lagrange’s Theorem). Now apply Mobius inversion and get: P_n = prod(d | n) (T^(q^n)-T)^(mobius(n/d)). This can be simplified further (for instance, once can replace T^(q^n)-T with T^(q^n – 1)-1 ).
  
  Comment by Ofir Gorodetsky — December 29, 2015 @ 7:51 pm | Reply
Consider the generating function $\displaystyle \zeta(z, t) = \sum_F z^{d(F)} F(t)$ where $F$ runs over all monic polynomials over $\mathbb{F}_q$ and $d(F)$ denotes the number of irreducible factors (with multiplicity) of $F$ (not the degree). It has an Euler product factorization

$\displaystyle \zeta(z, t) = \prod_P \left( \frac{1}{1 - z P(t)} \right)$

where the product runs over monic irreducible polynomials over $\mathbb{F}_q$ . Taking the logarithmic derivative with respect to $z$ gives

$\displaystyle \frac{\partial \zeta}{\partial z}(1, t) / \zeta(1,t) = \sum_P \frac{1}{1 - P(t)}$ .

Maybe someone can do something with this.

Comment by Qiaochu Yuan — December 29, 2015 @ 9:48 pm | Reply
- This is certainly an interesting manipulation, but the logarithmic derivative seems to be missing a factor of P(t) in the numerator. Also, if one tries to calculate the coefficient of z in the generating function zeta, one encounters an infinite sum of irreducible polynomials, and I don’t see any straightforward way to make sense of that sum.
  
  Comment by Partha Solapurkar — December 29, 2015 @ 11:40 pm | Reply
  - Nuts, you’re right. Fortunately, the two expressions differ by a constant, namely $\infty$ ! And yes, this is an entirely formal manipulation; I haven’t thought about what kind of convergence even in the sense of formal power series we have.
    
    Comment by Qiaochu Yuan — December 30, 2015 @ 1:03 am | Reply
  - It’s OK if we use $\zeta(z,t) := \prod_P (1 - z P(t)^{-1})^{-1} = \sum_F z^{d(F)} F(t)^{-1}$ instead, because there are finitely many $P$ of any given (positive) degree, and we’re working with power series in $1/t$ . Actually, this is (essentially) the approach discussed at the beginning of the original article (http://arxiv.org/pdf/1512.02685v1.pdf).
    
    Comment by Victor Wang — December 30, 2015 @ 1:15 am | Reply
My first thought is to rearrange the sum as
$\sum_{P \in \mathcal{P}} \sum_{k=1}^{\infty} \frac{1}{P^k} = \sum_{Q \in \mathcal{Q}} \frac{1}{Q}$
where $\mathcal{Q}$ is the set of perfect powers of irreducible polynomials. Then I might group the latter sum by the degree of $Q$ . Does this go anywhere?

Comment by David Speyer — December 29, 2015 @ 10:07 pm | Reply
Talking with John Voight, here’s a brief description of his computation (the results that Terry Tao summarized above):

He uses Magma to test each polynomial of degree n for irreducibility, and then if the polynomial is irreducible, he computes the corresponding power series to precision 45 (ignoring u^46 and above) and adds it to the running total. Overall, this takes 2^(n-1) iterations, and testing irreducibility costs soft-O(n^2) operations (presumably, this is the bottleneck of each iteration).

For reference, it took 19 days to perform these iterations for degree n=37. At this rate, we can expect the degree-38 calculation to take well over a month. By the “prime number theorem” for F_2, there are about 2^(n-1) irreducible polynomials of degree n, and so we’re stuck with exponential time unless we can avoid listing all irreducible polynomials.

Comment by Dustin G. Mixon — December 30, 2015 @ 12:47 am | Reply
- Correction: There are about (2^n)/n irreducible polynomials of degree n.
  
  Comment by Dustin G. Mixon — December 30, 2015 @ 12:55 am | Reply
  - Yep, it seems this could be optimized via Kudlaya-Umans. Their algorithm indicates improving irreducibility testing (via Rabin’s test) to more like O~(n log n) operations, for small fixed characteristic.
    
    Comment by John Nicol — December 30, 2015 @ 1:39 am | Reply
    - Is there an existing implementation of Kudlaya-Umans? I wonder how big the hidden constant is. (They improve upon an alternative whose time complexity involves the omega from matrix multiplication, so that’s a red flag…)
      
      Comment by Dustin G. Mixon — December 30, 2015 @ 1:47 am | Reply
      - I can’t find one online. According to some comments I’ve found in other papers, the constant probably swamps the algorithm with degrees this low.
        
        Not sure what the Magma application is doing under the covers for finite-field-polynomial irreducibility testing, as it’s closed-source — is it known to be efficient, even O(N^2), for this particular operation?
        
        Comment by John Nicol — December 30, 2015 @ 2:33 am | Reply
        
        The obvious test is to run IsIrreducible(f) for random polynomials f of various degrees and observe how the runtime scales. Perhaps an existing Magma-user will run the experiment? If not, I’ll download Magma and run it myself.
        
        Comment by Dustin G. Mixon — December 30, 2015 @ 3:15 am | Reply
I’m trying to figure out if the product formula for the Carlitz exponential is useful. (I usually would think about this sort of thing longer before posting it, but my understanding is that the etiquette of Polymath’s is to post half baked ideas.) A good reference is the book chapter here. In particular, see Theorem 3.2.8 and the material before it. I’ll summarize:

Let $q$ be a prime power. Put $[i] = T^{q^i}-T$ and $D_i = [i] [i-1]^q [i-2]^{q^2} \cdots [1]^{q^{i-1}}$ . Put $e(z) = \sum_{j=0}^{\infty} \tfrac{x^{q^j}}{D_j}$ . This is $t^{-1}$ -adically convergent for any $z$ in $\mathbb{F}_q(t)$ . Then we have

$\displaystyle{z \prod_{0 \neq a \in \mathbb{F}_q[z]} (1-z/a) = \frac{1}{\pi} e(\pi z)}$

where $\pi$ is a certain transcendent power series in $t$ , which can be found by comparing powers of $z^q$ .

The problem, of course, is that the product is over all nonzero polynomials, not just the irreducible ones. Comparing coefficients of $z^k$ on both sides gives some interesting identities though. For example, taking $q=2$ and comparing powers of $z^3$ , we get

$\sum \frac{1}{a_1 a_2}=0$

where the sum is over unordered pairs $\{ a_1, a_2 \}$ of distinct nonzero polynomials in $\mathbb{F}_2[t]$ . Putting $a = a_1 a_2$ , we can rewrite this as

$\sum \frac{\lfloor d(a)/2 \rfloor}{a}=0,$

where $d(a)$ is the number of divisors of $a$ .

Now, $d(a) \equiv 0 \bmod 4$ unless $a$ is a square or a prime times a square. So this sum isn’t so far from being a sum over primes …

That’s how far I’ve gotten so far.

Comment by David Speyer — December 30, 2015 @ 1:28 am | Reply
- I believe I have a proof. Let $A$ be the set of nonzero polynomials in $\mathbb{F}_2[x]$ . For any set $S$ , let $\binom{S}{2}$ be the set of unordered pairs of distinct elements of $S$ . As explained above, looking at the coefficient of $x^3$ in the product term for the Carlitz exponential shows that
  
  $\displaystyle{\sum_{\{ a_1, a_2 \} \in \binom{A}{2}} \tfrac{1}{a_1 a_2} = 0}$ .
  
  We can factor this as
  
  $\displaystyle{\sum_{d \in A} \frac{1}{d^2} \sum_{\substack{\{ a_1, a_2 \} \in \binom{A}{2} \\ GCD(a_1, a_2)=1}} \frac{1}{a_1 a_2} = 0}$ .
  
  Computing the first term up to order $t^{-1}$ shows that it is nonzero, so
  
  $\displaystyle{\sum_{\substack{\{ a_1, a_2 \} \in \binom{A}{2} \\ GCD(a_1, a_2)=1}} \frac{1}{a_1 a_2} = 0}$ .
  
  Let $\omega(f)$ be the number of distinct irreducible factors of $f$ . Then the number of ways to factor $f$ as $a_1 a_2$ with $\{ a_1, a_2 \} \in \binom{A}{2}$ is $2^{\omega(f)-1}$ (or $0$ if $f=1$ .) Since we are working modulo $2$ , the only terms which contribute to the sum are powers of irreducible polynomials. We obtain
  
  $\displaystyle{\sum_{p \in \mathcal{P}} \sum_{k=1}^{\infty} \frac{1}{p^k} = 0}$ .
  
  The inner sum is a geometric series, and we have
  
  $\displaystyle{\sum_{p \in \mathcal{P}} \frac{1}{p-1} = 0}$
  
  as desired.
  
  Comment by David Speyer — December 30, 2015 @ 10:40 am | Reply
  - Dear David, This is very nice!
    
    Comment by Gil Kalai — December 30, 2015 @ 11:23 am | Reply
  - I was rather confused by the phrase “Computing the first term up to order t^(-1)”. I get it now: By “term” you mean “factor”.
    
    Comment by Dustin G. Mixon — December 30, 2015 @ 4:22 pm | Reply
  - Wow, this is very nice! So it seems the general strategy is (a) to express sums over irreducible polynomials in terms of sums over all polynomials, by a finite characteristic version of “multiplicative number theory”, and then (b) to use the Carlitz product formula (or related machinery) to evaluate the resulting sums over all polynomials. The Carlitz stuff is new to me, this is something I will definitely try to learn more about (though not immediately, due to various holiday activities).
    
    Looks like this Polymath project is almost wrapping up before it even officially started… but I guess that’s a good “problem” to have.
    
    Comment by Terence Tao — December 31, 2015 @ 3:56 pm | Reply
Building on the ideas in my previous post, I can show that $\sum_{q \in Q} 1/q^k$ is in $\mathbb{F}_2(t)$ for any positive integer $k$ , where $Q$ is the set of powers of irreducible polynomials in $\mathbb{F}_2[t]$ . Once again, let $A$ be the set of nonzero polynomials in $\mathbb{F}_2[t]$ .
Let $K$ be the fraction field $\mathbb{F}_2(t)$ ,
let $e_j$ be the $j$ -th elementary symmetric polynomial and let $\pi = \sum_{a \in A} 1/a$ .

Lemma 1: For any positive integer $k$ , we have $e_k(1/a)_{a \in A} \in K \pi^k$ .

Proof: Look at the coefficient of $z^k$ in $\prod_{a \in A} (1+z/a) = e_C(\pi z)/(\pi z)$ , where $e_C$ is the Carlitz exponential.

Lemma 2: Let $F$ be any symmetric polynomial of degree $k$ with integer coefficients. Then $F(1/a)_{a \in A} \in K \pi^k$ .

Proof: The ring of symmetric polynomials is generated by the $e_k$ .

Lemma 3: The fraction $e_2(1/a^k)_{a \in A}/\sum_{a \in A} 1/a^{2k}$ is in $K$ .

Proof: By Lemma 2, the numerator and denominator are in $\pi^{2k} K$ . (And the denominator is nonzero, as every term except $a=1$ has no constant term.)

The fraction in Lemma 3 is $\sum_{q \in Q} 1/q^k$ by the same argument I used in the $k=1$ case. QED

If we replace $\mathbb{F}_2[t]$ by $\mathbb{F}_{2^j}[t]$ , the same method should work if $2k \equiv 0 \bmod q$ , $q = 2^j-1$ . Without this condition, the ratio in Lemma 3 is $0/0$ .

No ideas about odd characteristic yet.

I’m going to take a break from this for the rest of the day. Others are welcome to join in!

Comment by David Speyer — December 30, 2015 @ 6:07 pm | Reply
- The above should read $2k \equiv 0 \bmod 2^k-1$ , which is, of course, equivalent to $k \equiv 0 \bmod 2^k-1$ . [Corrected, – T.]
  
  Also, I am not taking a break, because I just figured out how to attack odd characteristic.
  
  Comment by David Speyer — December 30, 2015 @ 7:02 pm | Reply
Let $p$ be a prime, $r$ a power of $p$ . Let $A$ be the nonzero polynomials in $\mathbb{F}_r[t]$ , and let $Q$ be the powers of the irreducible ones (not assumed monic). The point of this post is to discuss computing $\sum_{q \in Q} 1/q^k$ is in $\mathbb{F}_r(t)$ . If $k \not \equiv 0 \bmod r-1$ , the sum is $0$ by grouping together scalar multiples of the same polynomial, so we may and do henceforth assume $k \equiv 0 \bmod r-1$ .

As before, let $A$ be the nonzero polynomials in $\mathbb{F}_r[t]$ . Let $\pi$ be a $(r-1)$ -st root of $\sum_{a \in A} 1/a^{r-1}$ in $\mathbb{F}_r((t))$ . Let $K = \mathbb{F}_r((t))$ .

Lemma 1: If $F$ is a degree $d$ symmetric polynomial with integer coefficients, then $F(1/a)_{a \in A}$ is in $\pi^d K$ .

Proof: As before.

Lemma 2: With our assumption that $k \equiv 0 \bmod r-1$ , we have $\sum_{a \in A} 1/a^k \neq 0$ .

Proof: The only summands with constant terms are from $a \in \mathbb{F}_r^{\ast}$ , and that sum is $r-1$ .

Let $f(x)$ be the symmetric polynomial $(e_1(x^k)^p - e_1(x^{kp}))/p$ . Note that $f$ has integer coefficients. So, by the lemmas, $f(1/a)_{a \in A} / e_{kp}(1/a)_{a \in A}$ makes sense and is in $K$ .

Expanding this out and factoring out GCD’s, this ratio is

$\displaystyle{ \frac{1}{p} \sum \frac{1}{a_1^k a_2^k \cdots a_p^k} }$

where the sum is over ordered $p$ -tuples with $GCD(a_1, \ldots, a_p) = 1$ and the $a_i$ not all equal, and the division by $p$ must be interpreted as grouping together terms which are rotations of each other. (The condition that the $a_i$ are not all equal just discards $(1,1,\ldots,1)$ .)

This is $\sum_{a \in A} \frac{\phi(a)/p}{a^k}$ , where $\phi(a)$ is the number of ways to factor $a$ as $a_1 a_2 \cdots a_p$ with $GCD(a_1, \ldots, a_p)=1$ . Again, we must compute $\phi(a)/p$ as an integer before reducing it to characteristic $p$ .

Up to a nuisance power of $r-1$ , we can easily see that $\phi(a)$ is a multiplicative function of $a$ . If $q$ is irreducible, then $\phi(q^e)$ is the number of ways to write $e = d_1+d_2 + \cdots + d_p$ , with the $d_i$ nonnegative integers and $\min(d_i)=0$ . This set has a free action of the cyclic group of order $p$ by rotating the $d_i$ , so $\phi(q^e)$ is divisible by $p$ . Thus, if $a$ is not a prime power, then $\phi(a) \equiv 0 \bmod p^2$ and doesn’t contribute to the sum

Thus, as before, we are left just summing over prime powers, although this time the sum depends on the exponent in the prime power in a more complicated way.

I’ve promised my daughter to read her a story now, so I’m stopping here.

Comment by David Speyer — December 30, 2015 @ 7:38 pm | Reply
- To finish up this note — Let $\psi(e)$ be the number of ways to write $e=d_1+d_2 + \cdots + d_p$ with all $d_i\geq 0$ and $\min d_i = 0$ . I believe the argument above shows that
  
  $\sum_{q \in \mathcal{P}} \sum_{e=1}^{\infty} \frac{\psi(e)/p}{q^{ke}}$
  
  is in $K$ . If I did the combinatorics right, I get two simpler formulas: I think this is also
  
  $\sum_{q \in \mathcal{P}} \sum_{e\not\equiv 0 \bmod p} \frac{1}{e q^{ke}}$
  
  and
  
  $\sum_{q \in \mathcal{P}} h(1/q^k)$
  
  where
  
  $h(x) = \frac{(1-x^p) - (1-x)^p}{p (1-x)^p}.$
  
  So, where does this go? Are there people besides me who want to think about this? What is left to be done?
  
  Comment by David Speyer — December 31, 2015 @ 12:00 am | Reply
  - Because of the zeta connection, I expected `something’ for any q.For odd characteristic, when the same thing did not seem to work numerically, I had tried a few simple linear
    combinations (one very close to the second displayed formula in this note), but it did not work
    without the proper circle of ideas that David has introduced!
    
    Comment by Dinesh S Thakur — December 31, 2015 @ 12:43 am | Reply
Excellent David! Your proofs generalize to class number one higher genus A’s with rational infinite
place and p=2 immediately (there are 4 of them without char. restriction, at least 2 or 3 in char. 2) and probably even more, with more work! May be somebody will see how to put characters and get algebraic things in more generality still.

These were the most interesting conjectures to me personally, but the preprint link has many more guesses/numerical observations at finite level which are still open and will need different methods to attack. Polymath community hopefully will settle them soon too. Thanks!

I just traveled to India, so unfortunately cannot edit and update (till 13th Jan) my webpage link as promised.
Sorry.

Comment by Dinesh S Thakur — December 31, 2015 @ 12:16 am | Reply
- Minor additional comments: Settling `vanishing’ part of conjectures (for example, the
  simplest case is vanishing for q=2^n, k=q-1, which follows easily by David’s proof in 14 applied to the
  product of scalar multiples (q-1 of them) of a monic polynomial), characterization of vanishing,
  explicit formulae for rationality, various conjectural or unknown results on prime power sums valuations
  and vanishing (many examples in preprint) are some areas where polymath talent can help in many ways.
  (I should say that I have not done thorough checks on these parts of conjectures and some are
  wild speculations, so it might be good to test them numerically much better to see whether they survive before serious attempt to prove!).
  
  There are also transcendence proving aspects when rationality or algebraically is not seen. (See preprint).
  
  Most exciting would be discovering some rationality/algebraicity in number fields prime sums of certain kind,
  by taking some clues from here. I only want to say that when I tried this numerically, I did get some surprising `close encounters’ (but not exact) and it might still be just possible!
  
  Comment by Dinesh S Thakur — December 31, 2015 @ 2:11 am | Reply
Congratulations to David Speyer for proving a big chunk of Dinesh’s conjecture!

In case there’s still a need to efficiently sum over degree- $d$ irreducibles
over a $q$ -element field $k$ :

Fix a convenient model of a degree- $d$ extension $K$ of $k$ , and a generator
$z$ of $K^*$ . (We don’t mind spending a good amount of time finding this
data because we need do it only once.) Then the irreducibles are in 1:1
correspondence with positive $m < p^d - 1$ such that for each $e=1,2,\ldots,d-1$
the remainder of $p^e m \bmod p^d-1$ strictly exceeds $m$ : such $m$
corresponds to the minimal polynomial of $z^m$ , namely
$\prod_{e=0}^{d-1} (X - \varphi^e(z^m))$ where $\varphi$ is the
$q$ -power Frobenius. This should also be reasonably straightforward
to parallellize.

Comment by Noam D. Elkies — December 31, 2015 @ 5:11 am | Reply
[…] Anna continues her investigation of irreducible polynomials over the finite field with 2 elements. In this installment, she works out the roots of all the irreducible polynomials of degrees 4 and 5. Anna’s entire investigation traces back to an exercise suggested by Prof. Judy Walker in her interview from Volume 8, Number 6. Do you think you can see where Anna might be headed? If you do, follow your thoughts and see where they lead. You’re invited to tell us about it; we’d love to hear from you. If you’re falling in love with polynomials over , check out this proposal for a new PolyMath project and the comments that follow. […]

Pingback by Girls’ Angle Bulletin, Volume 9, Number 2 | Girls' Angle — December 31, 2015 @ 5:06 pm | Reply
Just a remark: one only needs a small portion of the theory of the Carlitz exponential to run David’s argument in 14, one just needs to play with Moore matrices. For any degree $d$ , observe from the linearity of the Frobenius map $P \mapsto P^2$ that the vector $(P, P^2, P^{2^2}, \dots, P^{2^d})$ is a linear combination of the vectors $(T^j, T^{2j}, T^{2^2 j}, \dots, T^{2^d j})$ for $j=0,\dots,d-1$ whenever $P$ is a polynomial in $F_2[T]$ of degree at most $d-1$ (we include the case $P=0$ here). Therefore, the Moore determinant

$\displaystyle \det \begin{pmatrix} 1 & 1 & 1 & \dots & 1 \\ T & T^2 & T^{2^2} & \dots & T^{2^d} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ T^{d-1} & T^{2(d-1)} & T^{2^2(d-1)} & \dots & T^{2^d(d-1)} \\ X & X^2 & X^{2^2} & \dots & X^{2^d} \end{pmatrix}$

vanishes whenever $X$ is a polynomial of degree at most $d-1$ , giving $2^d$ distinct roots to this determinant. On the other hand, this determinant is clearly a polynomial in $X$ (with coefficients in $F_2[T]$ ) of degree $2^d$ . Thus, by the factor theorem, this determinant must equal a non-zero scalar multiple of $\prod_{\hbox{deg}(P) \leq d-1} (X-P)$ . On the other hand, the $X^3$ coefficient of the determinant is clearly zero. Therefore the $X^3$ coefficient of $\prod_{\hbox{deg}(P) \leq d-1} (X-P)$ vanishes, and hence the $X^2$ coefficient of $\prod_{\hbox{deg}(P) \leq d-1: P \neq 0} (X-P)$ vanishes. Dividing by the non-zero quantity $\prod_{\hbox{deg}(P) \leq d-1: P \neq 0} (-P)$ , we conclude that

$\sum_{\{P_1,P_2\} \in \binom{A_d}{2}} \frac{1}{P_1 P_2} = 0$

where $A_d$ is the set of non-zero polynomials of degree less than or equal to $d-1$ . Sending $d \to \infty$ , we obtain the identity

$\sum_{\{P_1,P_2\} \in \binom{A}{2}} \frac{1}{P_1 P_2} = 0$

that David used to prove the identity $\sum_{P \in {\mathcal P}} \frac{1}{1+P} = 0$ .

Comment by Terence Tao — January 1, 2016 @ 7:25 pm | Reply
- This gives a nice proof that $x \prod_{a \in A} (1+x/a) = \sum e_k x^{p^k}$ for some sequence $e_k$ . The further fact which I need in the later parts is that there is a series $\pi$ such that $e_k/\pi^{p^k-1}$ is in $\mathbb{F}_p(t)$ . Can you get that out of this?
  
  Comment by David Speyer — January 1, 2016 @ 10:37 pm | Reply
  - Yes, 14 needs only F_q linearity, and both that and the general fact needed with explicit pi (needs just a little more manipulation) as you mentioned were derived by Carlitz in his 1935 paper using exactly this
    Moore determinant technology and independently (without explicit formulas but in great generality) was achieved similarly again in Drinfeld’s 1974 paper. (There are expositions and variants
    in Goss’ and my books.)
    
    Not relevant here, but historically interesting fact is that
    some of the `higher rank Drinfeld modules theory was also developed by
    Carlitz (unpublished) and those `lecture notes’ were published by his student Hayes in Finite Fields and their applications special issue on carlitz.
    
    Comment by Dinesh S Thakur — January 2, 2016 @ 12:07 pm | Reply
Hi,

Very interested outsider here! Feel free to moderate out this comment if it is inappropriate, but this result seems incredible and raises many questions, including:

1) What are the implications of finding this structure among the irreducible polynomials over F2? Are the implications limited because of being over F2 and because of being polynomials?

2) Is there likely to be any structure at all among the interaction terms? If so/not, what are the implications?

3) The prime numbers are often treated as if they are distributed randomly. Is there any sense in which the terms in this problem are considered to be distributed randomly, and if so, what does the “vanishing” mean in this context?

4) Are there any immediate or indirect consequences for sums over the integers (in particular over the prime numbers)? I’m guessing not, but is there possibly a field and a formula for which the primes vanish?

5) Again back to the randomness question, and still not quite understanding how the distribution of irreducible polynomials would be represented, does a result like this have any implications for separating pseudo-random sequences from truly random sequences?

Comment by Ian Finn — January 2, 2016 @ 4:04 am | Reply
This sounds like an interesting discussion. I wish I had gotten to it a little earlier, so I could follow along better. The main thought I had was that some irreducible polynomials might be equivalent under different primes.

Comment by Jesse — January 4, 2016 @ 2:18 pm | Reply
At this point, I could either imagine this becoming a short project or a much longer one. The short version contains the proofs above, and also explicitly computes many of the sums. I would imagine the scope of that paper being $\mathbb{F}_q[T]$ for an arbitrary $q$ .

If it were to become much longer, here are two things which might be worth trying, and that I don’t intend to think about:

(1) Prof: Thakur points out to me via e-mail that the proofs also work for class number one higher genus A’s with one rational infinite place. That doesn’t seem like an interesting enough generalization to me to be worth putting as more than a remark. More interesting would be to get to higher genus A’s with one rational infinite place. The problem is that we want to sum over all maximal ideals, and some of them are not principal. But, we could look for formulas for sums like $\sum_{\pi \in \mathrm{Max}(A)} f(1/(\pi^h)^{q-1})$ . Here $\mathrm{Max}(A)$ is the maximal ideals of $A$ and $f$ is a rational function and $h$ is the class number. We interpret $\pi^h$ as meaning any generator of the principal ideal $\pi^h$ . Any two such generators differ by an element of $\mathbb{F}_q^{\times}$ , so $(\pi^h)^{q-1}$ is well defined.

(2) It would be worth checking whether there are more rational identities to be found, which are not obvious consequences of the above. For example, set $f_k = \sum_{P \in \mathcal{P},\ \deg(P) \equiv k \bmod p} 1/P^{q-1}$ . Are any $\mathbb{F}_q$ -linear combinations of the $f_k$ rational, other than $\sum f_k/k$ ? (We could search for this using continued fractions.) More generally, we could look for a linear relation $\sum c_k(T) f_k=0$ with $c_k$ in $\mathbb{F}_q(T)$ . (Is there some sort of LLL algorithm for $\mathbb{F}_q[T]$ ?)

After all, I just came up with the first symmetric function I could think of to extract the irreducible polynomials; there may be many others.

Comment by David Speyer — January 5, 2016 @ 9:07 pm | Reply
- (3) We might as well check that nothing happens if you sum over just the monic representatives of the irreducible polynomials. That’s what I’d expect, based on the analogy to the $\zeta$ function, but I wouldn’t have guessed these formulas if I hadn’t seen them either.
  
  Comment by David Speyer — January 6, 2016 @ 1:49 am | Reply
- (1) Getting more relations of this type showing new symmetries in prime distribution sounds like the top priority and most suitable for polymath, as different people can check different things (I had tried some linear combinations without success, and meant such things when `putting in characters’ was mentioned!). (2) Characterization of vanishing (rather than
  only rationality) and explicit formula families (as in k=2^n-1 part of conj. B) would be very interesting. Again diffferent
  people can work on different parts (different q’s for example, checking last part of conjecture C, which is a little
  wild, but very effective. If true, proving it would be very nice! Cleaner combinatiorial characterization for that part
  would also be very nice. ). (3) As for class no. 1, it is a remark since David’s beautiful proofs work straight (I had numerical evidence, but not solid), without which it was unclear whether it was rational function field phenomena or more.
  
  Comment by Dinesh S. Thakur — January 6, 2016 @ 4:09 am | Reply
I’ve put up a draft paper explaining the results I sketched above at http://www.math.lsa.umich.edu/~speyer/PolymathIdentities.pdf . Comments, large and small, are very welcome.

Obviously, it still needs some editing to be arXiv ready (and shortly thereafter, submission ready), but I mostly want to get this off of my to-do list soon. This paper also shows how far I want to go with this as a research project. If someone out there has cool ideas beyond what I’ve written, they are very welcome to pursue them, and I won’t compete with them.

As you can see, I am planning to make this a solo paper (with Terry and Dinesh’s permission). I hope no one will feel cheated by that, it seems reasonable to me.

Comment by David Speyer — January 11, 2016 @ 7:30 pm | Reply
- I just looked at this. Can you write down the derivation of $\sum \frac{1}{1+P} = 0$ anyway? Even though you have proven something more general. What are some examples of $\pi$ in your function field? It just says all coefficients “match”
  
  Comment by John Mangual — January 18, 2016 @ 2:54 pm | Reply
  - I didn’t think the paper was interesting enough to be worth writing up the p=2 case separately, but you can see it as my December 30, 2015 @ 10:40 am post above. Comparing coefficients of $x^{q-1}$ , we have $\frac{\pi^{q-1}}{T^q-T} = - \sum_{a \in A_1} \frac{1}{a^{q-1}}$ , where $A_1$ is the monic polynomials. (This is analogous to defining the archimedean $\pi$ by $\frac{\pi^2}{6} = \sum_{a \in \mathbb{Z}_{\geq 0}} \frac{1}{a^2}$ .
    
    Comment by David Speyer — January 19, 2016 @ 2:41 pm | Reply
- Interesting to whom? Certainly we are all here because we found this problem (kind of) interesting. Personally I find lots of things interesting and fall into the trap of assuming other people will be interested as well.
  
  Actually… not in any rush here. For now, I am content reading your comments and just knowing that p=2 case is true.
  
  Comment by John Mangual — January 19, 2016 @ 6:20 pm | Reply
I think it should be a solo paper. You have already included an appropriate acknowledgement section. I would try to avoid the unfortunate alliteration/homophones “Some sums” though…

Comment by sdf — January 13, 2016 @ 12:42 pm | Reply
[…] on the polymath blog, I’ve posted (on behalf of Dinesh Thakur) a new polymath proposal, which is to explain some numerically observed identities involving the irreducible polynomials in […]

Pingback by A new polymath proposal: explaining identities for irreducible polynomials | TRIFORCE STUDIO — January 20, 2016 @ 5:23 am | Reply
[…] very nice polymath proposal by Dinesh Thakur was posted by Terry Tao on the polymath blog. The task was to explain some […]

Pingback by News (mainly polymath related) | Combinatorics and more — January 20, 2016 @ 6:22 am | Reply
[…] question of whether to call it Polymath11 (the first unclaimed number) or Polymath12 (regarding the polynomial-identities project as Polymath11). In the end I’ve gone for Polymath11, since the polynomial-identities project […]

Pingback by FUNC1 — strengthenings, variants, potential counterexamples | Gowers's Weblog — January 29, 2016 @ 2:41 pm | Reply
[…] beautiful polymath proposal by Dinesh Thakur was posted by Terry Tao on the this blog. The task was to explain some […]

Pingback by Explaining Polynomials Identities – Success! | The polymath blog — February 7, 2016 @ 3:03 am | Reply
The last update is nearly two months old. I wonder whether David’s paper is already on arxiv or submitted? I couldn’t find anything on arxiv. thanks!

Comment by Timmon Spear — April 4, 2016 @ 9:15 pm | Reply
- Thakur updated his article on this with Speyer’s argument: http://arxiv.org/abs/1512.02685
  
  Comment by Terence Tao — April 4, 2016 @ 9:51 pm | Reply
  - Further updates are and will be at my webpage at the link mentioned in the arxive version. Anybody who knows of or makes further progress is
    requested to let me know. Thanks! —Dinesh
    
    Comment by Dinesh S Thakur — April 5, 2016 @ 1:16 pm | Reply
  - Thanks! Does that mean that David Speyer won’t publish an article on that anymore, if Thakur has used his arguments in his paper?
    
    Comment by Timmon Spear — April 10, 2016 @ 2:03 pm | Reply
    - Ah ok, i thought it’s a two-author paper now. just saw it doesnt give the proof by speyer, but continues working useing that new technique. Is there still work in progress in Speyers paper or is it already submitted?
      
      Comment by Timmon Spear — April 10, 2016 @ 2:09 pm | Reply

RSS feed for comments on this post. TrackBack URI

	Cherrypick India on Polymath projects 2021
	tanner808 on Polymath projects 2021
	Anonymous on Polymath 11 is Now Open
	Chenxiao Tian on Polymath 11 is Now Open
	ryeguy10 on Polymath 11 is Now Open
	ndnnnd on Polymath projects 2021
	Prime time on Two polymath (of a sort) propo…
	What comes after exp… on Minipolymath2 project: IMO 201…
	Will AI Replace Math… on Spontaneous Polymath 14…
	gui7575 on A new polymath proposal (relat…
	Thomas Vu on Polymath projects 2021
	Mary Megrant on Polymath projects 2021
	h0sane on A sort of Polymath on a famous…
	Thomas Vu on Polymath projects 2021
	Hyun seok on A sort of Polymath on a famous…

The polymath blog

December 28, 2015