[proofplan] To each nonempty subset $J \subseteq \{1, \ldots, k\}$ we associate a parity signature in $\{0,1\}^{r+1}$ recording the parities of the exponents of $-1$ and of each $p_i$ in $c_J := \prod_{i \in J} c_i$. The hypothesis $k > r + 1$ ensures there are more singleton subsets than available signatures, so the pigeonhole principle yields two distinct subsets $J \neq K$ with the same signature. Multiplying $c_J c_K$ cancels the square-free part, and a clean combinatorial identity rewrites the product so that the symmetric difference $I := J \triangle K$ indexes a subset whose product is a perfect square. [/proofplan] [step:Define the parity signature of a subset] Fix the ordering $p_0 := -1, p_1, \ldots, p_r$ of the sign together with the $r$ allowed primes. For any nonempty $J \subseteq \{1, \ldots, k\}$, set \begin{align*} c_J := \prod_{i \in J} c_i \in \mathbb{Z} \setminus \{0\}. \end{align*} Since each $c_i$ has prime factors only among $\{p_1, \ldots, p_r\}$ and is nonzero, the same is true of $c_J$. Hence there exist a unique sign bit $\alpha_{J,0} \in \{0,1\}$ (with $\alpha_{J,0} = 1$ iff $c_J < 0$), unique exponents $e_{J,i} \in \mathbb{Z}_{\geq 0}$ for $i = 1, \ldots, r$, and a unique positive integer $m_J \geq 1$ such that writing $\alpha_{J,i} \in \{0,1\}$ for the parity of $e_{J,i}$, \begin{align*} c_J = (-1)^{\alpha_{J,0}} \, p_1^{\alpha_{J,1}} \cdots p_r^{\alpha_{J,r}} \, m_J^2. \end{align*} We then define the parity signature map \begin{align*} \sigma : 2^{\{1,\ldots,k\}} \setminus \{\varnothing\} &\to \{0,1\}^{r+1} \\ J &\mapsto (\alpha_{J,0}, \alpha_{J,1}, \ldots, \alpha_{J,r}). \end{align*} [guided] The key idea is that an integer $n \neq 0$ whose prime factors lie in $\{p_1, \ldots, p_r\}$ is a perfect square if and only if the exponent of every $p_i$ in its prime factorisation is even, and $n > 0$. To detect squareness, we therefore only need to track $r + 1$ bits per integer: the sign, plus the parity of each exponent. Concretely, for any nonempty $J \subseteq \{1, \ldots, k\}$ we form the product $c_J := \prod_{i \in J} c_i$, which is a nonzero integer with prime factors in $\{p_1, \ldots, p_r\}$. By unique factorisation in $\mathbb{Z}$, we may write \begin{align*} c_J = (-1)^{\alpha_{J,0}} \, p_1^{\alpha_{J,1}} \cdots p_r^{\alpha_{J,r}} \, m_J^2, \end{align*} where $\alpha_{J,0} \in \{0,1\}$ is the sign bit, each $\alpha_{J,i} \in \{0,1\}$ is the parity of the exponent of $p_i$ in $c_J$, and $m_J \geq 1$ absorbs all even contributions. This decomposition is unique: $\alpha_{J,0}$ is determined by $\operatorname{sgn}(c_J)$, and each $\alpha_{J,i}$ is the reduction of the $p_i$-adic valuation $v_{p_i}(c_J)$ modulo $2$. The parity signature of $J$ is the vector \begin{align*} \sigma(J) := (\alpha_{J,0}, \alpha_{J,1}, \ldots, \alpha_{J,r}) \in \{0,1\}^{r+1}. \end{align*} By construction, $c_J$ is a perfect square if and only if $\sigma(J) = (0, 0, \ldots, 0)$. [/guided] [/step] [step:Apply the pigeonhole principle to find two subsets with equal signature] The codomain $\{0,1\}^{r+1}$ has exactly $2^{r+1}$ elements. The $k$ singleton subsets $\{1\}, \{2\}, \ldots, \{k\}$ of $\{1, \ldots, k\}$ are pairwise distinct. By hypothesis $k > r + 1$, and since $r + 1 \leq 2^{r+1}$ fails in general but we only need a stronger statement: we have $k > r + 1$, which does not immediately give $k > 2^{r+1}$. We therefore enlarge the collection of inputs. Consider instead the family of all $2^k - 1$ nonempty subsets of $\{1, \ldots, k\}$. Since $k > r + 1 \geq 1$, we have $k \geq 2$ and hence $2^k - 1 \geq 3 > 2$, which is not yet enough. The correct pigeonhole count uses $k \geq r + 2$ and the identity $2^k - 1 \geq 2^{r+2} - 1 > 2^{r+1}$, so the number of nonempty subsets strictly exceeds the number of possible signatures. Hence the map \begin{align*} \sigma : \{J \subseteq \{1, \ldots, k\} : J \neq \varnothing\} \to \{0,1\}^{r+1} \end{align*} cannot be injective, and there exist distinct nonempty subsets $J, K \subseteq \{1, \ldots, k\}$ with $J \neq K$ and $\sigma(J) = \sigma(K)$. [guided] We want to apply the [pigeonhole principle](/theorems/???): any map from a set of size $N$ to a set of size $M$ with $N > M$ must collapse two inputs to the same output. Our codomain $\{0,1\}^{r+1}$ has exactly $2^{r+1}$ elements, so we need a domain of more than $2^{r+1}$ nonempty subsets. How many nonempty subsets does $\{1, \ldots, k\}$ have? Exactly $2^k - 1$. We claim $2^k - 1 > 2^{r+1}$ under the hypothesis $k > r + 1$, equivalently $k \geq r + 2$ (since all quantities are integers). Indeed, $k \geq r + 2$ gives $2^k \geq 2^{r+2} = 2 \cdot 2^{r+1}$, hence \begin{align*} 2^k - 1 \geq 2 \cdot 2^{r+1} - 1 > 2^{r+1}. \end{align*} Therefore the number of nonempty subsets exceeds the number of parity signatures, and $\sigma$ cannot be injective on this domain. Pick two distinct nonempty subsets $J \neq K$ with $\sigma(J) = \sigma(K)$. (The simpler argument using only the $k$ singletons works when $k > 2^{r+1}$, but our hypothesis $k > r + 1$ is weaker. Fortunately the larger collection of $2^k - 1$ subsets is still available, and it is always sufficient.) [/guided] [/step] [step:Combine signatures multiplicatively to produce a square exponent vector] Having $\sigma(J) = \sigma(K)$ means $\alpha_{J,i} = \alpha_{K,i}$ for every $i \in \{0, 1, \ldots, r\}$. Multiplying the factorisations, \begin{align*} c_J \cdot c_K &= \left[ (-1)^{\alpha_{J,0}} \prod_{i=1}^r p_i^{\alpha_{J,i}} \cdot m_J^2 \right] \cdot \left[ (-1)^{\alpha_{K,0}} \prod_{i=1}^r p_i^{\alpha_{K,i}} \cdot m_K^2 \right] \\ &= (-1)^{2\alpha_{J,0}} \prod_{i=1}^r p_i^{2\alpha_{J,i}} \cdot (m_J m_K)^2 \\ &= \prod_{i=1}^r p_i^{2\alpha_{J,i}} \cdot (m_J m_K)^2 \\ &= \left( \prod_{i=1}^r p_i^{\alpha_{J,i}} \cdot m_J m_K \right)^2. \end{align*} In particular $c_J c_K$ is a perfect square of the positive integer $M := \prod_{i=1}^r p_i^{\alpha_{J,i}} m_J m_K$. [/step] [step:Rewrite $c_J c_K$ via the symmetric difference identity] For any two subsets $J, K \subseteq \{1, \ldots, k\}$, \begin{align*} \prod_{i \in J} c_i \cdot \prod_{i \in K} c_i &= \prod_{i \in J \cap K} c_i^2 \cdot \prod_{i \in J \triangle K} c_i, \end{align*} where $J \triangle K = (J \setminus K) \cup (K \setminus J)$ denotes the symmetric difference and we use the convention that an empty product equals $1$. Indeed, for each $i \in \{1, \ldots, k\}$, the exponent of $c_i$ in the left-hand side is $\mathbb{1}_J(i) + \mathbb{1}_K(i) \in \{0, 1, 2\}$, which equals $2$ when $i \in J \cap K$ and $1$ when $i \in J \triangle K$ — matching the right-hand side term by term. Substituting into the equality from the previous step and writing $c_{J \cap K} := \prod_{i \in J \cap K} c_i$ (with $c_\varnothing := 1$) and $c_{J \triangle K} := \prod_{i \in J \triangle K} c_i$, \begin{align*} c_{J \cap K}^2 \cdot c_{J \triangle K} = c_J c_K = M^2. \end{align*} [guided] The symmetric difference identity is a standard bookkeeping move. To see it, consider any index $i \in \{1, \ldots, k\}$ and count how many times $c_i$ appears on each side: - If $i \in J \cap K$: it appears once from $\prod_{i \in J} c_i$ and once from $\prod_{i \in K} c_i$, giving exponent $2$ on the left. On the right, it appears as $c_i^2$ in the first product. Match. - If $i \in J \setminus K$: it appears once on the left. On the right, $i \in J \triangle K$ contributes $c_i$ once. Match. - If $i \in K \setminus J$: symmetric. - If $i \notin J \cup K$: absent from both sides. So the identity holds term by term, hence as integers. Applying it with our specific pair $(J, K)$, and combining with the square expression $c_J c_K = M^2$ from the previous step, \begin{align*} \left( \prod_{i \in J \cap K} c_i \right)^2 \cdot \prod_{i \in J \triangle K} c_i = M^2. \end{align*} The left factor is itself a square (of a nonzero integer, since each $c_i$ is nonzero). Setting $c_{J \cap K} := \prod_{i \in J \cap K} c_i$ and $c_{J \triangle K} := \prod_{i \in J \triangle K} c_i$ gives $c_{J \cap K}^2 \cdot c_{J \triangle K} = M^2$. [/guided] [/step] [step:Isolate the symmetric difference product and verify it is nonempty] From the identity $c_{J \cap K}^2 \cdot c_{J \triangle K} = M^2$, we have $c_{J \cap K} \neq 0$ (as a product of nonzero integers, using $c_\varnothing := 1$ when $J \cap K = \varnothing$). Hence we may divide: \begin{align*} c_{J \triangle K} = \frac{M^2}{c_{J \cap K}^2} = \left( \frac{M}{c_{J \cap K}} \right)^2. \end{align*} Since $c_{J \triangle K} \in \mathbb{Z}$ and its value as a rational square equals an integer square up to sign, in fact $M / c_{J \cap K} \in \mathbb{Q}$ and $c_{J \triangle K} \in \mathbb{Z}$ is a perfect square of a rational number; because $c_{J \triangle K}$ is an integer whose rational square root $M/c_{J \cap K}$ is rational, $M / c_{J \cap K}$ is in fact a (possibly negative) integer. Thus $\prod_{i \in J \triangle K} c_i$ is the square of an integer. It remains to check that $I := J \triangle K$ is nonempty. Since $J \neq K$, there exists an index in exactly one of $J$ and $K$, i.e., $J \triangle K \neq \varnothing$. Therefore $I = J \triangle K \subseteq \{1, \ldots, k\}$ is a nonempty subset with $\prod_{i \in I} c_i$ a perfect square, completing the proof. [guided] We have $c_{J \cap K}^2 \cdot c_{J \triangle K} = M^2$ from the previous step. Since each $c_i \neq 0$, the product $c_{J \cap K}$ over the intersection is a nonzero integer (and equals $1$ if $J \cap K = \varnothing$). Dividing both sides by $c_{J \cap K}^2$ yields \begin{align*} c_{J \triangle K} = \frac{M^2}{c_{J \cap K}^2}. \end{align*} The right-hand side is a rational square of $M / c_{J \cap K}$. But $c_{J \triangle K}$ is an integer. An integer that equals a rational square is in fact a perfect square of an integer: if $a \in \mathbb{Z}$ and $a = (p/q)^2$ in lowest terms, then $aq^2 = p^2$, so $q^2 \mid p^2$, hence $q \mid p$, forcing $q = 1$ (since $\gcd(p,q) = 1$). Therefore $M/c_{J \cap K}$ is an integer, and $c_{J \triangle K}$ is its square. Finally, we must confirm that the index set $I := J \triangle K$ is nonempty, else "the subset $I$" would be empty and the assertion $\prod_{i \in I} c_i = 1$ trivially a square (with $1 \in J \triangle K$ undefined). Since $J$ and $K$ are distinct subsets of $\{1, \ldots, k\}$, there is some $i$ belonging to exactly one of them, so $i \in J \triangle K$ and $I \neq \varnothing$. Thus $I = J \triangle K$ is a nonempty subset of $\{1, \ldots, k\}$ for which $\prod_{i \in I} c_i$ is a perfect square. [/guided] [/step]