Verification of Conjecture 6.2 for all moduli t^n-1 with t^n less than 3*10^9

The data file lists the various moduli t^n-1 (t and n positive integers with t > 1) that it checked.  It does not check any t such that t=b^k for some integers b and k with b < t, because the truth of the conjecture for modulus b^(k*n)-1 implies the truth of the conjecture for modulus t^n-1 by Remark 6.3 and it is assumed that b^(k*n)-1 modulus has already been checked.

For each modulus checked, the program runs through all possible values of d in Conjecture 6.2, proceeding in order of t-ary weight.  The program skips d that are not congruent to 1 modulo t-1, for Conjecture 6.2 is automatically verified for these by Lemma 6.7.

Among those d with the same t-ary weight, the program proceeds in numerical order.  For any integer k, t^k*d reduced modulo t^n-1 (a cyclic shift of d modulo t^n-1 in t-ary notation) will trivially verify Conjecture 6.2 if and only if d verifies it.  So we shall later apply a filter that skips d (as already having been checked) if d is not the least such cyclic shift.   We do not go to any value of d so high that it is obvious that some cyclic shift of it modulo t^n-1 will be lower than d itself.

Since d^(-1) (modulo t^n-1) and its cyclic shifts also verify Conjecture 6.2 if and only if d does, we shall later apply a filter that skips d (as having already been checked) if d^(-1) has lower t-ary weight that d, or equal t-ary weight but lower numerical value.

The program only checks those d with t-ary weight less than or equal to floor(n/2)*(t-1).  For if d has higher weight than this, and if it is assumed that d^(-1) (mod t^n-1) has equal or greater weight than d, then there will be some j and k as described in Lemma 6.6, thus verifying Conjecture 6.2.

Once we restrict to such d, there are various filters employed which filter out all d that either do not meet the hypotheses of the conjecture or for which the program can verify the conjecture.  The program lists how many of the d values checked are filtered out by a particular filter, recording the number of d not filtered by any filter as the number of "losses."  For the moduli checked, we have no losses, thus verifying the conjecture for all moduli under consideration.

We now describe the specific filters:

The filter "niho" checks if d is not a power of t modulo t^m-1 for some m < n, in which case it is assumed that the conjecture has already been verified for this smaller modulus, and thus (by Lemma 6.5 of the paper) also verified for the current modulus, and hence filtered out.

The filter "shift" checks if there is a k such that t^k*d (mod t^n-1) (which has the same spectrum of Weil sum values as d) is lower than d, and hence has already been checked, so that d can be filtered out.

The filter "coprime" checks if d is not coprime to t^n-1, so that the conjecture is verified for d by Lemma 6.4, and so such a d is filtered out.

The filter "gwws" (short for "gap, wrap, weight, shift") checks the following four things: (1) ["gap"] Checks if there is a j and k such that Lemma 6.6 verifies the conjecture. (2) ["wrap"] If we use [k] to denote the least nonnegative integer congruent to k modulo n, and if d=d_0+d_1 t + ... + d_{n-1} t^{n-1} and d^(-1) (mod t^n-1)=e_0+e_1 t + ... + e_{n-1} t^{n-1} with 0 <= d_i, e_i < t for all i, then this filter checks to see if the sum over all j and k of d_j*e_k t^[j+k] is greater than t^n, because if it is greater, then there is some a strictly covered by d^(-1) such that d*d^(-1)=1 is strictly covered by d*a, thus verifying Conjecture 6.2.  To find such an a, begin with a=0 and modify it by adding powers of t such that your modified a is still covered by d^(-1) and stop as soon as the value of a has the property that the sum over all j and k of d_j*a_k t^[j+k] exceeds t^n (where a=a_0+a_1 t + ... + a_{n-1} t^n with 0 <= a_i < t for all i).  This a will not be d^(-1) itself, for then your sum over j and k would need to be at least 2*t^n-1, but adding a single power of t cannot make the sum over j and k increase from something strictly less than t^n to something at least 2*t^n-1.  Furthermore, the sum of d_j*a_k t^[j+k] is divisible by t (because if it were not, then there would have been a j and k that would cause d to be filtered out by the "gap" filter above), but the sum is at least t^n and less than 2*t^n-1, so when you reduce it modulo t^n-1, you get a number that has a 1 in the t^0 place in its t-ary expansion, hence d*a (mod t^n-1) (which is the reduction of the sum modulo t^n-1) covers 1.  And since a is not d^(-1) itself, d*a (mod t^n-1) will not be 1, so the covering is strict.  So any d that has passed through the "gap" filter and such that the sum over all j and k of d_j*e_k*t^[j+k] is greater than t^n, then that d can be filtered out.  (3) ["weight"] Checks if t-ary weight of d^(-1) (which satisfies the conjecture if and only if d does) is larger than that of d, and hence has already been checked, so that d can be filtered out. (4) ["shift"] If the t-ary weight of d^(-1) is equal to that of d, the filter "shift" checks if there is a k such that t^k*d^(-1) (mod t^n-1) (which satisfies the conjecture if and only if d does) is lower than d, and hence has already been checked, so that d can be filtered out.

The filter "two bit" checks if there are a and b such that a and d*b (mod t^n-1) have t-ary weight 2 and such that a and b verify Conjecture 6.2 for d, so that d can be filtered out.

The filter "consec" checks if there are a and b where a is of the form 1+t+...+t^k (with k>=2) such that a and b verify Conjecture 6.2 for d, so that d can be filtered out.

The filter "hard" checks exhaustively to see if there are a and b that verify Conjecture 6.2 for d, so that d can be filtered out.