login
A261524
Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2).
5
3, 7, 9, 15, 21, 27, 31, 33, 35, 39, 45, 49, 51, 57, 63, 69, 73, 75, 77, 81, 85, 87, 91, 93, 99, 105, 111, 117, 119, 123, 127, 129, 133, 135, 141, 147, 153, 155, 159, 161, 165, 171, 175, 177, 183, 189, 195, 201, 203, 207, 213, 217, 219, 225, 231, 237, 243, 245, 249, 255, 259, 261, 267, 273, 279, 285, 287, 291, 297, 301
OFFSET
1,1
COMMENTS
From the Golomb/Lee reference: "Theorem 7 (Welch’s Criterion): For any odd integer t, the irreducible polynomials of primitivity t divide trinomials iff gcd( 1 + x^n, 1 + (1+x)^n ) has degree greater than 1."
All Mersenne numbers (A000225) >= 3 are terms, as all primitive polynomials (over GF(2)) divide some trinomial.
All numbers of the form (2j-1)*(2^k-1); j>=1, k>=2 (A261871), are in the sequence. - Bob Selcoe, Sep 03 2015
From Robert Israel, Sep 03 2015: (Start)
If n is in the sequence, then so is every odd multiple of n, because 1+x^n divides 1+x^(k*n) and 1+(1+x)^n divides 1+(1+x)^(k*n).
The first few members of the sequence that are not multiples of other members are 3, 7, 31, 73, 85, 127, 2047, 3133, 4369, 8191, 11275 (see A261862). (End)
From Jianing Song, Oct 13 2023: (Start)
Also odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 0. This is because degree(gcd( 1 + x^n, 1 + (1+x)^n )) cannot be 1 since gcd( 1 + x^n, 1 + (1+x)^n ) is divisible by neither x nor x+1.
In general, let p be a prime, gcd(m,p) = 1, q > 1 be a power of p that is congruent to 1 modulo m. In the finite field F_q, the roots to x^m-1 are the nonzero ((q-1)/m)-th powers, so gcd(x^m-1, (x+1)^m-1) != 1 if and only if there are two nonzero ((q-1)/m)-th powers in F_q that differ by 1. If we homogenize, this is equivalent to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) having solutions in (F_q)* (dehomogenize by setting y = 1).
Let p be a prime, gcd(m,p) = 1. Suppose that q > 1 is the smallest power of p that is congruent to 1 modulo m, then gcd(x^m-1, (x+1)^m-1) != 1 in F_p[x] if m > q^(3/4): set k = (q-1)/m and A_1, A_2 both be the set of nonzero ((q-1)/m)-th powers in F_q (so |A_1| = |A_2| = m). Let N be the number of solutions to x^((q-1)/m) + y^((q-1)/m) = z^((q-1)/m) has solutions in (F_q)*, then by Theorem 7.1 of the László Babai link, we have N > m^2*(q-1)/q - (q-1)*sqrt(q) >= 0.
In particular, let p and r be distinct primes, r >= 5, t >= 1. Let Zs(d,p,1) is the d-th Zsigmondy number with parameters (p,1), then gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) != 1 in F_p[x]. This is because for d != 2, Zs(d,p,1) = Phi_d(p)/r if d is of the form r^{t'}*ord(p,r) and Phi_d(p) otherwise (see A323748), where ord(a,k) is the multiplicative order of a modulo k, Phi_d(x) is the d-th cyclotomic polynomial. Here d = r^t, so Zs(d,p,1) = Phi_d(p)/r if p == 1 (mod r), Phi_d(p) otherwise. Note that Phi_{r^t}(p) = 1 + p^(r^(t-1)) + p^(2*r^(t-1)) + ... + p^((r-1)*r^(t-1)) > q^(3/4) = p^(3/4*r^t) since r >= 5. It is easy to show that Zs(p^r,p,1) <= q^(3/4) can only happen with r = 5, p == 1 (mod 5) and p <= 601, then we can check that gcd(x^(Zs(r^t,p,1))-1, (x+1)^(Zs(r^t,p,1))-1) = gcd(x^((p^4+p^3+p^2+p+1)/5)-1, (x+1)^((p^4+p^3+p^2+p+1)/5)-1) != 1 in F_p[x] in this case.
For another example, m = (2^(2^t)+1)*(2^(2^(t+1))+1) is a term of this sequence for all t >= 0, since in the case we have q = 2^(2^(t+2)), so m = q^(3/4) + 2^(2^(t+1)) + 2^(2^t) > q^(3/4).
Conjecture 1: Zs(d,2,1) is a term if and only if d is odd and d != 1, 15, 21. Verified for odd numbers up to 91.
Conjecture 2: for a prime p >= 3, gcd(x^(Zs(d,p,1))-1, (x+1)^(Zs(d,p,1))-1) != 1 if and only if d is an odd prime power > 1 other than (d,p) = (7,3), (7,9), (13,3), (37,3), (43,3), (79,3).
Note that the comment above shows that both conjectures are true for powers > 1 of a prime r >= 5. (End)
LINKS
László Babai, The Fourier Transform and Equations over Finite Abelian Groups, Department of Computer Science, University of Chicago.
Solomon W. Golomb and Pey-Feng Lee, Irreducible Polynomials Which Divide Trinomials over GF(2), IEEE Transactions on Information Theory, vol.53, no.2, pp.768-774 (February-2007).
MAPLE
filter:= proc(n) degree(Gcd(1+x^n, 1+(1+x)^n) mod 2)>1 end proc:
select(filter, [2*i+1 $ i=1..200]); # Robert Israel, Sep 03 2015
MATHEMATICA
okQ[n_] := Exponent[PolynomialGCD[1+x^n, 1+(1+x)^n, Modulus -> 2], x] > 1;
Select[Range[1, 301, 2], okQ] (* Jean-François Alcover, Apr 02 2019 *)
PROG
(PARI) W(n)=my(e=Mod(1, 2)); poldegree(gcd(e*(1+x^n), e*(1+(1+x)^n))) > 1;
forstep(n=1, 301, 2, if( W(n) , print1(n, ", ") ) );
(Sage)
x = polygen(GF(2), 'x')
[n for n in range(1, 10^3, 2) if gcd( 1+x^n, 1+(1+x)^n ).degree() > 1]
# Joerg Arndt, Sep 08 2015
(PARI) isA261524(n, p=2) = my(d=znorder(Mod(p, n)), c=ffgen(p^d, 'c), g=ffprimroot(c)); forstep(e=0, p^d-2, (p^d-1)/n, if((g^e+1)^n==1, return(1))); return(0) \\ Jianing Song, Oct 14 2023, based on the equivalence of gcd(x^m-1, (x+1)^m-1) != 1 and two ((q-1)/m)-th powers in F_q differing by 1 (see Comments)
CROSSREFS
Note that A191131, A261524, A261871, and A282572 are very similar and easily confused with each other.
Sequence in context: A099204 A219608 A070993 * A261871 A191131 A282572
KEYWORD
nonn
AUTHOR
Joerg Arndt, Aug 23 2015
STATUS
approved