login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A261524 Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2). 5

%I #74 Oct 16 2023 16:15:06

%S 3,7,9,15,21,27,31,33,35,39,45,49,51,57,63,69,73,75,77,81,85,87,91,93,

%T 99,105,111,117,119,123,127,129,133,135,141,147,153,155,159,161,165,

%U 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

%N Odd numbers n such that degree(gcd( 1 + x^n, 1 + (1+x)^n )) > 1, where the polynomials are over GF(2).

%C 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."

%C All Mersenne numbers (A000225) >= 3 are terms, as all primitive polynomials (over GF(2)) divide some trinomial.

%C All numbers of the form (2j-1)*(2^k-1); j>=1, k>=2 (A261871), are in the sequence. - _Bob Selcoe_, Sep 03 2015

%C From _Robert Israel_, Sep 03 2015: (Start)

%C 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).

%C 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)

%C From _Jianing Song_, Oct 13 2023: (Start)

%C 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.

%C 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).

%C 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.

%C 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.

%C 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).

%C 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.

%C 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).

%C Note that the comment above shows that both conjectures are true for powers > 1 of a prime r >= 5. (End)

%H Joerg Arndt, <a href="/A261524/b261524.txt">Table of n, a(n) for n = 1..23300</a>

%H László Babai, <a href="https://people.cs.uchicago.edu/~laci/reu02/fourier.pdf">The Fourier Transform and Equations over Finite Abelian Groups</a>, Department of Computer Science, University of Chicago.

%H Solomon W. Golomb and Pey-Feng Lee, <a href="http://dx.doi.org/10.1109/TIT.2006.889714">Irreducible Polynomials Which Divide Trinomials over GF(2)</a>, IEEE Transactions on Information Theory, vol.53, no.2, pp.768-774 (February-2007).

%p filter:= proc(n) degree(Gcd(1+x^n, 1+(1+x)^n) mod 2)>1 end proc:

%p select(filter, [2*i+1 $ i=1..200]); # _Robert Israel_, Sep 03 2015

%t okQ[n_] := Exponent[PolynomialGCD[1+x^n, 1+(1+x)^n, Modulus -> 2], x] > 1;

%t Select[Range[1, 301, 2], okQ] (* _Jean-François Alcover_, Apr 02 2019 *)

%o (PARI) W(n)=my(e=Mod(1,2)); poldegree(gcd(e*(1+x^n), e*(1+(1+x)^n))) > 1;

%o forstep(n=1,301,2, if( W(n) , print1(n,", ") ) );

%o (Sage)

%o x = polygen(GF(2), 'x')

%o [n for n in range(1, 10^3, 2) if gcd( 1+x^n, 1+(1+x)^n ).degree() > 1]

%o # _Joerg Arndt_, Sep 08 2015

%o (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)

%Y Cf. A261871, A261862.

%Y Note that A191131, A261524, A261871, and A282572 are very similar and easily confused with each other.

%K nonn

%O 1,1

%A _Joerg Arndt_, Aug 23 2015

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 08:22 EDT 2024. Contains 371236 sequences. (Running on oeis4.)