Let p be a prime number and let A be a set of positive integers that satisfies the following conditions:
(i) the set of prime divisors of the elements in A consists of p−1 elements;
(ii) for any nonempty subset of A, the product of its elements is not a perfect p-th power.
What is the largest possible number of elements in A ?
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
Let our primes be q1,q2,…,qp−1. By considering the exponents of each prime, our problem reduces to finding the largest number of (not necessarily distinct) p−1-tuples of elements in Z/pZ such that the sum of any set of elements in the set of them is not (0,0,…,0) mod p.
We have that k=(p−1)2. (p−1)2 is attainable, as the set {(1,0,0,…,0)⏟p−1 times ,(0,1,0,…,0)⏟p−1 times ,…,(0,0,0,…,1)⏟p−1 times } works.
We will now show that with (p−1)2+1 tuples, we can find a non-empty set of them that sum to 0. Let the elements of our set be T1=(e1,1,e2,1,…,ep−1,1),T2=(e1,2,e2,2,…,ep−1,2),…,T(p−1)2+1=(e1,(p−1)2+1,e2,(p−1)2+1,…,ep−1,(p−1)2+1).
Consider the following system of equations in the (p−1)2+1 variables a1,a2,…,a(p−1)2+1:
\begin{align*}
a_1^{p-1} e_{1,1} + a_2^{p-1} e_{2, 1} + \cdots + a_{p-1}^{p-1} e_{p-1,1} &\equiv 0 \pmod{p} \\
a_1^{p-1} e_{1,2} + a_2^{p-1} e_{2, 2} + \cdots + a_{p-1}^{p-1} e_{p-1,2} &\equiv 0 \pmod{p} \\
& \vdots \\
a_1^{p-1} e_{1,(p-1)^2 + 1} + a_2^{p-1} e_{2, (p-1)^2 + 1} + \cdots + a_{p-1}^{p-1} e_{p-1,(p-1)^2 + 1} &\equiv 0 \pmod{p}.
\end{align*}.
The sum of the degrees of this equation is (p-1)^2 < (p-1)^2 + 1. This system has the solution (a_1, a_2, \ldots, a_{p-1}) = (0, 0, \cdots, 0), so we may apply Chevalley's theorem to find a solution (a_1, a_2, \ldots, a_{p-1}) in which not each entry of the tuple is 0 modulo p.
Let a_{b_1}, a_{b_2}, \ldots, a_{b_n} be the nonzero entries. Note that a_i^{p-1} \equiv 0 \pmod{p} iff i \neq b_j for any j, and it is 1 iff i = b_j for some j. Therefore, we have that
\begin{align*}
e_{b_1, 1} + e_{b_2, 1} + \cdots + e_{b_n,1} &\equiv 0 \pmod{p} \\
e_{b_1, 2} + e_{b_2, 2} + \cdots + e_{b_n, 1} &\equiv 0 \pmod{p} \\
& \vdots \\
e_{b_1, (p-1)^2 + 1} + e_{b_2, (p-1)^2 + 1} + \cdots + e_{b_n, (p-1)^2 + 1} &\equiv 0 \pmod{p}
\end{align*}
It follows that the sum of the T_{b_1}, T_{b_2}, \ldots, T_{b_n} is (0,0,\ldots,0) mod p, so our proof is complete.
Solution from Twitch Solves ISL:
Let D = p-1. Then the question (thinking in terms of the exponents) can be phrased as follows:
What's the largest multiset of vectors in {\mathbb F}_p^{D} such that no nonempty subset has zero sum?
We claim the answer is D \cdot (p-1). A construction is given by taking
p-1 copies of the vector \left< 1, 0, \dots, 0\right>;
p-1 copies of the vector \left< 0, 1, \dots, 0\right>;
\dots;
p-1 copies of the vector \left< 0, 0, \dots, 1 \right>.
To show it's best possible, suppose we have vectors v_1, \dots, v_N with coordinates given as v_k = \left< v_{k,1}, v_{k,2}, \dots, v_{k,D} \right> \qquad k = 1, 2, \dots, N. Then, we construct the polynomial F(X_1, \dots, X_N) = \prod_{i=1}^D \left[ 1 - \left( \sum_{k=1}^N X_k v_{k,j} \right)^{p-1} \right] - \prod_{i=1}^N (1-X_i) If we imagine the X_i \in \{0,1\} as Bernoulli random variables indicating whether v_k is used in a set or not, then F(X_1, \dots, X_N) \neq 0 exactly when the X_i's equal to 1 correspond to a nonempty subset of the vectors which have vanishing sum.
Now assume for contradiction N < D \cdot (p-1). Then the largest degree term is given in the latter product; it is exactly (-1)^{N+1} X_1 X_2 \dots X_N. So if we quote Alon's combinatorial nullstellensatz, it now follows that there is a choice of X_i \in \{0,1\} such that F(X_1, \dots, X_N) \neq 0 which is a contradiction.
Solution with derfu37 and a hint to use Chevalley's from Al3jandro0000.
We claim the answer is (p-1)^2. This is achievable by taking the set
A = \{ q_i^{pj+1}\vert(i,j)\in\{1,\ldots,p-1\}^2 \} where \{q_i\}_{i=1}^{\infty} is the sequence of primes. Now we show |A|>(p-1)^2 is impossible. Let n=|A|. Note that by condition (i) we can represent the elements of A as vectors in \mathbb F_p^{p-1}. Let these be
v_i = (e_{i1},\ldots,e_{i(p-1)})\text{ for } 1\le i\le n. Now, we define f_j\colon\mathbb F_p^n\rightarrow\mathbb F_p^n as
f_j(x_1,\ldots,x_n) = \sum_{i=1}^n x_i^{p-1}e_{ji}. Consider the system of equations f_j(x_1,\ldots,x_n)=0 for 1\le j\le p-1. Note that (0,\ldots,0) is a trivial solution. Suppose for the sake of contradiction that n>(p-1)^2. Then, we have
n>(p-1)^2=(p-1)\cdot(p-1)=\sum_{j=1}^{p-1}\deg(f_j). Thus, quoting Chevalley's Theorem there must exist a nontrivial solution to the system. However, since x_i^{p-1}\in{0,1}, this nontrivial solution specifies a nonempty subset of A for which the product is a perfect p-th power, yielding the desired contradiction. \blacksquare
One can easily rephrase this problem using the prime factorizations of the elements of A; this asks for the size of the largest multiset of vectors of \mathbb{F}_p^{p-1} where no nonempty subset has a sum of zero.
The answer is (p-1)^2; this can be obtained by taking\bigcup_{\textbf{x}\in \mathbb{F}_p^{p-1} \\ |\textbf{x}|=1}\{\textbf{x} \ \text{repeated} \ p-1 \ \text{times}\}.Assume for contradiction that there is a solution of vectors v_1, \ldots, v_N with N>p-1 that works, where we write v_i = (e_{i1},\ldots,e_{i(p-1)}) for each i. Now define f_k(x_1,\ldots,x_N) = \sum_{i=1}^N x_i^{p-1}e_{ki} for all 1 \le k \le p-1. Since (0, \ldots, 0) is a common root of all f_k, the Chevalley-Warning theorem guarantees a nontrivial root common to all f_k. By Fermat's Little Theorem, each x_i^{p-1} is either 0 or 1, so there is a nonempty subset of \{v_1, \ldots, v_N\} with a zero sum by using this nontrivial root, a contradiction. Hence (p-1)^2 is the size of the largest multiset of vectors of \mathbb{F}_p^{p-1} where no nonempty subset has a sum of zero, and we are done.
Chevalley-Warning essentially nukes this.
The answer is (p-1)^2. For construction, pick primes q_1, q_2, \cdots, q_{p-1}, and use q_1, q_1^{p+1}, \cdots, q_1^{1+p(p-2)} and similarly for the other q_i's. This obviously satisfies both conditions.
For the proof of maximality, set the q_i to be the same and choose k = (p-1)^2 + 1 distinct elements from A, which we will label x_1 through x_k. For each j, let e_{ij} be the exponent of q_i in x_j.
Now, for the polynomials f_i(X_1, \cdots, X_k) = X_1^{p-1}e_{i1} + X_2^{p-1}e_{i2} + \cdots + X_k^{p-1} e_{ik},by Chevalley-Warning there exists a nontrivial solution to the system f_1(x_1, x_2, \cdots, x_k) \equiv f_2(x_1, x_2, \cdots, x_k) \equiv \cdots \equiv 0 \pmod p.Pick a subset B of all nonzero x_i in this set that satisfy the condition. Then by definition and Fermat's Little Theorem it follows that \sum_{j \in B} e_{ij} \equiv 0 \pmod p for each i, thus the product of the elements in B is a perfect pth power, contradiction.
Claim: If x_j = (x_{j,1},\cdots, x_{j,n}) \in (\mathbb{Z}/p\mathbb{Z})^n (j\in \{1,\cdots,K\}) such that for all e_1, \cdots, e_K \in \{0,1\} (not all zero), then \sum e_jx_j \ne 0. Then K\le n(p-1) (this bound is optimal because I can have p-1 copies of (\underbrace{0, \cdots, 0}_{j}, 1, \underbrace{0, \cdots, 0}_{n-1-j}) for j=0,\cdots,n-1)
Proof: Assume K\ge n(p-1)+1. Consider the polynomial
P(f_1, \cdots, f_K) = \prod\limits_{j=1}^n (1-(\sum_{k=1}^K f_kx_{k,j})^{p-1})
If \sum e_jx_j \ne 0 \iff there exists t such that \sum_k e_k x_{k,t} \ne 0. Then 1-(\sum_k e_k x_{k,t})^{p-1}=0 in \mathbb{Z}/p\mathbb{Z}. Hence P(f_1,\cdots,f_K)=0 for all f_1,\cdots,f_k \in \{0,1\} that are not all zero, and P(0,\cdots,0)=1.
We first flatten the polynomial i.e. replace f_k^j with f_k when j\ge 2 (i.e. we take this polynomial and take its remainder mod f_1^2-f_1, f_2^2-f_2, \cdots, f_K^2-f_K). Call this polynomial \tilde P. Now note \tilde P + (1-f_1)(1-f_2)\cdots (1-f_K)vanishes in \{0,1\}^K, but one can show that v\colon [K] \to (\mathbb{Z}/p\mathbb{Z})^{2^K}, v_S = ( \prod\limits_{j\in S} f_j )_{(f_1,\cdots,f_k)\in \{0,1\}^K}are linearly independent in \{0,1\}^K (or we induct by seeing this as a linear poly in f_1 namely R(f_2,\cdots,f_K) f_1 + Q(f_2,\cdots,f_K) and since this poly is 0 when f_1\in \{0,1\}, R(f_2,\cdots,f_K), Q(f_2,\cdots,f_K) satisfy the problem conditions for K-1) so \tilde P + (1-f_1)(1-f_2)\cdots (1-f_K) \equiv 0
This is absurd since \deg \tilde P < K
Yet another C-W nuke solution
Claim: |A| = (p-1)^2 is achieveable.
Proof. Let p_n denote the nth prime for 1 \le n \le p - 1. Then p-1 occurences of each p_n suffices. \blacksquare
Claim: (p-1)^2 is maximal.
Proof. FTSOC assume there exists some A of size n = p^2 - 2p. Enumerate A as a_{1}, a_{2}, \dots, a_n and the prime divisors as p_1, p_2, \dots, p_n. For each i, let a_i = p_1^{c_{i1}}p_2^{c_{i2}}\dots p_n^{c_{in}}.
Construct the p-1 polynomials f_1, f_2, \dots f_{p-1} in {\mathbb F}_p such that f_i(x_1, x_2, \dots, x_n) = \sum_{j=1}^{n} c_{ij}x_j^{p-1}. Note that \deg f_i = p-1 and that f_i is 0 iff the elements of A at its nonzero inputs have a product with \nu_{p_i} divisible by p.
Since n > \deg f_i \cdot (p-1) = (p-1)^2, and (0, 0, \dots, 0) is one of the common roots of every polynomial, by Chevalley-Warnining there exists another root, contradiction. \blacksquare
Let D = p-1. Then the question (thinking in terms of the exponents) can be phrased as follows:
What's the largest multiset of vectors in {\mathbb F}_p^{D} such that no nonempty subset has zero sum?
We claim the answer is D \cdot (p-1). A construction is given by taking
p-1 copies of the vector \left< 1, 0, \dots, 0\right>;
p-1 copies of the vector \left< 0, 1, \dots, 0\right>;
......;
p-1 copies of the vector \left< 0, 0, \dots, 1 \right>.
To show it's best possible, suppose we have vectors v_1, \dots, v_N with coordinates given as v_k = \left< v_{k,1}, v_{k,2}, \dots, v_{k,D} \right> \qquad k = 1, 2, \dots, N. Then, we construct the polynomial F(X_1, \dots, X_N) = \prod_{i=1}^D \left[ 1 - \left( \sum_{k=1}^N X_k v_{k,j} \right)^{p-1} \right] - \prod_{i=1}^N (1-X_i) If we imagine the X_i \in \{0,1\} as Bernoulli random variables indicating whether v_k is used in a set or not, then F(X_1, \dots, X_N) \neq 0 exactly when the X_i's equal to 1 correspond to a nonempty subset of the vectors which have vanishing sum.
Now assume for contradiction N < D \cdot (p-1). Then the largest degree term is given in the latter product; it is exactly (-1)^{N+1} X_1 X_2 \dots X_N. So if we quote Alon's combinatorial nullstellensatz, it now follows that there is a choice of X_i \in \{0,1\} such that F(X_1, \dots, X_N) \neq 0 which is a contradiction. \square
The answer is (p-1)^2
Interpret each number as a \mathbb{F}_p^{p-1} vector with entries corresponding to their \nu_q modulo p: we are asked to find the largest multiset of vectors such that no nonempty subset of them sum to the 0 vector. For a construction, we may take p-1 copies of each of the p-1 vectors with one entry equal to 1 and the rest 0.
I will now prove that k:=|A|>(p-1)^2 is impossible. To that end, suppose we had k vectors v_1,\ldots,v_k and the j-th element of v_i was a_{ij}. Consider the following polynomial in \mathbb{F}_p[x_1,\ldots,x_k]:
P(x):=\prod_{i=1}^{k} (1-x_i)-\prod_{j=1}^{p-1} \left(1-\left(\sum_{i=1}^k a_{ij}x_i\right)^{p-1}\right).If we restrict x_i \in \{0,1\} for all i, then choosing some subset of the vectors and summing them is equivalent to setting some subset of the x_i to 1 (and the rest 0). If we choose the empty set, i.e. x_i=0 always, then the first and second products are both 1. Otherwise, the first product clearly vanishes, and by hypothesis, since some entry of their sum is nonzero, Fermat's little theorem guarantees that the second product vanishes as well. Thus P vanishes for any choice of (x_1,\ldots,x_k) \in \{0,1\}^k, but since k>(p-1)^2 it contains the maximal-degree term (-1)^kx_1\ldots x_k, which yields a contradiction by combinatorial nullstellensatz. \blacksquare