A007789-A007792: the originating problem, after thirty years

[Zoltan Reti]

Hi Sequence Fans,

In 1994, when I was at U Florida, I contributed four sequences,
A007789-A007792, under the description
"From a problem concerning circulant matrices and Gauss sums".

I did not say what the problem was, and since July 2020 the
entries have carried the candid editorial note that "it is not clear
from what problem concerning circulant matrices and Gauss sums the
terms of the sequence come". Several editors attached references in
the hope of decoding them.

After some 30 years ("Nel mezzo del cammin di nostra vita..."),
I would like to state the problem and give its solution.

For x = (x_0,...,x_{d-1}) let circ(x) be the d X d circulant matrix of
x, and put

    g_d(n) = (1/n) * Sum_{x in (Z/nZ)^d} exp(2*Pi*i*det(circ(x))/n).

At a prime p not dividing d, the value depends only on how u^d - 1 factors over GF(p),
hence only on p mod d.

If d = 3 the determinant is our old friend x^3 + y^3 + z^3 - 3*x*y*z.

For this d, if p is a prime, the value is
2*p-1 when p == 1 (mod 3) and 1 when p == 2 (mod 3),
so g_3(7) = 7^2 - 6^3/6 = 2*7 -1 = 13;
the seventh term of A007789, as displayed since 1994.

The value is always a rational integer for reasons given in the paper,
and n -> g_d(n) is multiplicative, but not completely multiplicative:
g_3(4) = 4 but g_3(2)^2 = 1.


When d is square-free, I have theorems for g_d(n) at every n.
When p^2 divides d, I still have theorems for g_d(p) and g_d(p^2),
but for g_d(p^k), k>=3 , I had to strain my computer hardware to compute the values
and try to find rules.
(I have 128 GB DDR5 and 16 GB GPU - these are my limitations.)

For example, I have computed

    g_9(3^k) = 0, 3^15, 3^23, 3^30, 3^38   for k = 1,...,5.

But g_9(3^6) is beyond me, so I have the g_9 sequence without any holes
through g_9(728) only.

Anyone with more hardware, you are welcome to expand our knowledge.


A paper giving the closed forms sequence by sequence, with b-files to
10^4 terms, with PARI and Mathematica programs, is at

    doi:10.5281/zenodo.21969895

and a book with the fuller theory
(where an extra parameter - let us call it twist - shows up as well) is at

    doi:10.5281/zenodo.21970262

I have proposed edits to the entry A007789 (d=3),
and they are in the editorial queue at oeis.org.

(A007790  (d=4), A007791  (d=5), A007792  (d=6) will come next)

Thanks for your attention,

Zoltan Reti
Budapest, Hungary

[DONG HAOXUAN]

Hi Zoltan,

I had a look at the d = 9, p = 3 case you mentioned.

The pattern in the first few values actually breaks at k = 6:

g₉(3⁶) = 2·3⁴⁵,

so it is not 3⁴⁵.

I was also able to get a formula for all later powers:

g₉(3ᵏ) = (2k - 13)·3⁷ᵏ⁺³ for k ≥ 7.

Together with your computed values for k = 1,...,5, this gives the full 3-power subsequence.

The proof uses a 3-adic decomposition of the circulant determinant and reduces the calculation to 81 conductor classes, so it does not require a direct computation at k = 6. I also made a separate verifier and had the proof independently checked.

I have put the proof and verification files together in a small package. If you are interested, I would be happy to send it over.

Best,
Jason Dong

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/0387e9a5-d096-476e-b03c-82a4ce003117n%40googlegroups.com.

[Zoltan Reti]

Hi Jason,

Thank you, and yes, please send the package.
I would very much like to see the proof and the verifier.

I am glad someone picked up the continuation of the 3-power column at d = 9.  
If the proof holds I will acknowledge you by name in the paper
I am preparing for the Journal of Integer Sequences, and in the OEIS entry,
as having first computed g_9(3^6) and given the general law.

My questions:

#1. The coefficient at k = 7:

Are you sure of the coefficient in

   g_9(3^k) = (2k-13) * 3^(7k+3),   k >= 7 ?

The reason I am asking is that your own k = 6 value and my k = 5 value
both sit exactly on (k-4) * 3^(7k+3):

   k = 5 :  3^38     = 1 * 3^(7*5+3)      k-4 = 1     2k-13 = -3
   k = 6 :  2 * 3^45 = 2 * 3^(7*6+3)      k-4 = 2     2k-13 = -1

so (k-4) needs no exceptional case at k = 6 at all, while (2k-13) fits
neither of the two values we already have. It is also the same
coefficient as the d = 4 law below, with the same shape:

   d = 4 :  (k-4) * 2^(2k+2)     k >= 5
   d = 9 :  (k-4) * 3^(7k+3)     k >= 5

The exponent is (d-2)k + p in both cases, and the linear factor
vanishes at the last head index k = 4.

The two readings first disagree at k = 7:
3 * 3^52 against 1 * 3^52.
Could you run that one term through your verifier?
If it comes out 1 * 3^52 then d = 9 genuinely departs from d = 4.

#2. A test vector:

The case d = 4, p = 2 is the same situation one prime down (p^2 | d).
I have checked it by direct enumeration to k = 8,

   g_4(2^k) = 0, 2^5, 2^8, 2^11, 1*2^12, 2*2^14, 3*2^16, 4*2^18,

and then, using the factorization det = (a^2-b^2)(c^2+e^2) with
a = x0+x2, c = x0-x2, b = x1+x3, e = x1-x3, which turns the sum into two
FFTs and reduces the cost from O(n^4) to O(n log n), out to k = 23.

The coefficients of 2^(2k+2) run
1,2,3,...,17,18,19    for k = 5,6,7,...,21,22,23;
with no exceptions and no sign changes.

If your 3-adic decomposition specializes to p = 2, this is an easy
check of your apparatus against values that are certain.

I have also reconfirmed g_9(9) = 3^15 by a second, independent route, so
that "anchor" at least is solid on both sides.

#3. What are the 81 conductor classes?

I assume they index the gluing of Z[u]/(u^9-1) inside
Z x Z[zeta_3] x Z[zeta_9] at 3, but I would rather hear it from you than
guess.

If you can say enough about the reduction for me to implement it
independently, I would like to do that, because two implementations
agreeing is worth more than one.

Direct verification at k = 6 is out of reach for anybody:
729^9 is about 1.5*10^26 terms.

An idea how to send the package:
If you deposit it in zenodo.org, you get a DOI and a timestamp,
which fixes your priority and gives me something citable for the
acknowledgement in the paper and in the OEIS entry.

Looking forward to the package,

Zoltan Reti

[DONG HAOXUAN]

Hi Zoltan,

Thank you. I have attached the proof and verification package.

On your first question: yes, I rechecked k = 7. The verifier gives

g_9(3^7) = 3^52,

so the coefficient is 1, not 3. Thus the formula is indeed

g_9(3^k) = (2k - 13) * 3^(7k+3), for k >= 7.

So the d = 9 case really does depart from the (k - 4) pattern at k = 7.

The 81 classes come from the local 3-adic gluing. In the notation used in the proof, the relevant order Lambda sits inside the product order B with

[B : Lambda] = 81,

and the conductor has depths (2,3,3). The verifier explicitly constructs all 81 representatives, checks that there are no collisions, and rebuilds their signature counts and the resulting generating function from scratch.

The easiest way to check the package is simply to run

./run_all.sh

It verifies the hashes, reconstructs the 81 classes, checks the conductor data, derives the values including g_9(3^6) = 2*3^45, and checks the closed formula through k = 60.

I would be very interested to see the result of your independent implementation as well.

And thank you very much for offering to acknowledge the result in the paper and OEIS entry. I appreciate that.

Best,
Jason Dong

To view this discussion visit https://groups.google.com/d/msgid/seqfan/61aa99fc-91de-4ef1-82a0-f2907ce5f1a1n%40googlegroups.com.

[Zoltan Reti]

Hi Jason,

Your formula for d=3^2 is correct and helped find the general formula.

Your method for d=3^2 is also correct and  carries over
(with some modifications) to any odd prime p.
I have a proof for p = 2 as well.

So the general formula is:

For every prime p, writing d = p^2:

  g_{p^2}(p^k) = 

                    0                                       for k = 1 ;

                    1 * p^ceil((2*p^2-3)*k/2)                   for 2 <= k <= 2*p-1 ;
                    2 * p^ceil((2*p^2-3)*k/2) = 2*p^((2*p^2-3)*p) for k =  2*p ;
                    ((p-1)*k - (2*p^2-p-2)) *     p^((p^2-2)*k+p)   for k >= 2*p+1 ;


Some special cases:

p =  2:  ( 1*k-  4) *  2^(  2*k+ 2),  k >=  5   ;  
    p =  3:  ( 2*k- 13) *  3^(  7*k+ 3),  k >=  7      (yours);
    p =  5:  ( 4*k- 43) *  5^( 23*k+ 5),  k >= 11 ;
    p =  7:  ( 6*k- 89) *  7^( 47*k+ 7),  k >= 15 ;
p = 11:  (10*k-229) * 11^(119*k+11),  k >= 23 ;
p = 13:  (12*k-323) * 13^(167*k+13),  k >= 27 ;

So we have closed the last gap in the d = 4 case (A007790)
and in general in the d = p^2 cases.

Your contribution is acknowledged here, and
will be acknowledged in the new edition of my book "Multiple Gauss Sums, Volume I."

The full proof for every d = p^2
(norm surjectivity, the conductor computation, and the signature census)
will also appear there.

Thank you again,

Zoltan Reti