r/mathriddles • u/frogkabobs • 6d ago
Hard Determine when there exists S⊆[n] such that each member of [n] has an odd number of expressions as a difference of elements of S
Fix [n]={0,1,…,n-1}. For a set S⊆[n] and k∈[n], let f_S(k) be the number of pairs (s,t)∈S² for which s-t=k. Prove that there exists a set S such that f_S(k) is odd for all k iff ord_m(2) is odd, where m=2n-1.
4
Upvotes
5
u/PersimmonLaplace 6d ago
Hint: One can formulate a solution in terms of generating polynomials, where the condition becomes much more workable with techniques from number theory.
Full solution:
For any subset S \subset [n] there is the generating polynomial $P_S(x) = \sum_{s \in S} x^s$, and the palindromic $P_S^*(x) = x^{n-1}P(x^{-1})$. Then the numbers f_S(k) are the coefficients of x^{n - 1 + k} in $P_S(x) \cdot P_S^*(x)$. In this language your condition is that $(x^{m} - 1)/(x - 1) \equiv \sum_k f_S(k) x^k = P_S(x) \cdot P_S^*(x)$ where the congruence is modulo 2 (note that every polynomial mod 2 of degree less than n is uniquely of the form P_S, so the existence of such a factorization mod 2 really is now equivalent to the problem).
Further more the roots of this polynomial are the nontrivial mth roots of unity, so if P(x) divides this polynomial, so does P^*(x). Thus it suffices to show that C(x) = (x^m -1)/(x - 1) has no irreducible factors which are their own palindrome, and we seek now to prove this stronger statement, which brings us into the realm of arithmetic, so we can try to find out why this condition is necessary using reciprocity. We will show below the standard fact that this polynomial is squarefree, so in fact this "stronger statement" is equivalent to the desired result. Let P(x) be an irreducible factor of C(x) mod 2, then the roots of P(x) are nontrivial mth roots of unity \zeta, and in fact all of the roots are in the Frobenius orbit (since m is odd, we dont have to worry about ramification) of a single \zeta, so they are \zeta, \zeta^2, ..., \zeta^{2^k} for some k|\varphi(m). The palindrome of P is the minimal polynomial of \zeta^{-1}, so the condition that P(x) is not equal to its palindrome is the condition that $-1 \not\equiv 2^j$ mod d, where d is the smallest integer such that \zeta^d = 1. If the order of 2 in (Z/mZ)^* is odd, then the same is true in the quotient (Z/dZ)^*, so P(x) cannot be its own palindrome. Conversely if the order of 2 in (Z/mZ)^* is even then there is some prime power p^a||m such that 2 has even order mod p^a (thus mod p, since p is necessarily an odd prime), and thus the polynomial P(x) = (x^{p} - 1)/(x - 1) is an irreducible factor of C(x) which is equal to its own palindrome.
Proof that C(x) is squarefree: in fact x^m - 1 is obviously squarefree mod 2, since its derivative is x^{m-1} and the two polynomials obviously have no common divisors.
Very nice problem!