What is the smallest size of a set $S$ with some extra conditions such that $S$ contains an $n$-th power residue for each prime $p$?

Question

This post is inspired by this one. I have two related questions.

Definition. Let $n$ be a positive integer. For an integer $m$ and $a$, we say that $a$ is an $n$-th power residue modulo $m$ if $$x^n\equiv a\pmod{m}$$ has a solution $x\in\mathbb{Z}$. A subset $S\subseteq \mathbb{Z}$ is said to be $n$-th power saturated if, for each prime natural number $p$, $S$ contains an $n$-th power residue modulo $p$.

Examples. The set of all prime natural numbers itself is $n$-th power saturated for every positive integer $n$. The set $\{2,3\}$ is not $n$-th power saturated for $n\in\{2,3,4\}$ (i.e., it is not quadratic-saturated, cubic-saturated, or quartic-saturated).

Question 1. For each positive integer $n$, what is the smallest cardinality of an $n$-th power saturated subset $S$ of the set of positive integers $\mathbb{Z}_{>0}$ such that
(a) $S$ contains no $n$-th perfect powers? (Let the answer be $A_n$.)
(b) $S$ contains no perfect powers at all? (Let the answer be $B_n$.)
(c) $S$ contains only squarefree integers? (Let the answer be $C_n$.)

Question 2. Does there exist a finite set $S$ containing integers greater than $1$ such that $S$ is $n$-th power saturated for any positive integer $n$?

Update. The answer is no. See Carl Schildkraut's answer below.

Known Results. Obviously, $$A_n\leq B_n\leq C_n\,.$$ From this answer, we know that $$C_n\leq \dfrac{n(n+1)}{2}\,.$$ It is known that $$A_2=B_2=C_2=3$$ due to Chebotarev's Theorem. (I have not seen a proof of this claim about the case $n=2$, so a reference for this would be appreciated.) From user760870's comment below, we can see that $$B_4\leq 6\,,$$ by taking $S=\{2,3,6,12,18,24\}$. The same user claimed in the same comment that $$A_n=B_n=n+1\text{ if $n$ is prime}\,,$$ with $S=\{2,3,6,12,\ldots,3\cdot 2^{n-1}\}$ as an example (I understand why this choice of $S$ works, but I cannot yet prove that this set $S$ has the lowest possible cardinality). It is easy, however, to verify that $$A_{8}=1\,,$$ by taking $S=\{16\}$, per the comment by user760870. Consequently, $$A_{2^k}=1\text{ for all }k=3,4,5,\ldots\,,$$ by taking $S=\left\{2^{2^{k-1}}\right\}$.

This is a proof that $A_8=1$, where $S=\{16\}$ works. Note that $$x^8-16=(x^2-2)(x^2+2)(x^4+4)\,.$$ - If $p=2$, then $x=0$ is a trivial solution.
- If $p\equiv 1 \pmod{8}$ or $p\equiv 7\pmod{8}$, then $x^2-2\equiv 0\pmod{p}$ has a solution $x\in\mathbb{Z}$.
- If $p\equiv 3\pmod{8}$, then $x^2+2\equiv 0\pmod{p}$ has a solution $x\in\mathbb{Z}$.
- If $p\equiv 5\pmod{8}$, then let $t\in\mathbb{Z}$ satisfy $t^2+1\equiv0\pmod{p}$, and note that $2t$ is a quadratic residue modulo $p$ (since both $2$ and $t$ are not). Therefore, $x^2-2t\equiv 0\pmod{p}$ has a solution $x\in\mathbb{Z}$, whence $$x^4+4\equiv (x^2-2t)(x^2+2t)\pmod{p}$$ implies that $x^4+4\equiv0\pmod{p}$ has a solution $x\in\mathbb{Z}$.
From this result, we can then conclude that $A_{2^k}=1$ with $S=\left\{2^{2^{k-1}}\right\}$, where $k\geq 3$ is a positive integer. This is because $x^{2^k}-2^{2^{k-1}}$ is divisible by $x^8-16$. In fact, $$x^{2^k}-2^{2^{k-1}}=(x^2-2)\,\prod_{j=1}^{k-1}\,\left(x^{2^j}+2^{2^{j-1}}\right)=(x^8-16)\,\prod_{j=3}^{k-1}\,\left(x^{2^j}+2^{2^{j-1}}\right)\,.$$

Answer 1

Here's an elementary answer to question 2.

We claim that no set of positive integers, each of which is strictly between $1$ and $k$ is $(p-1)$-th power saturated for any prime $p>k$. Indeed, for such a set $S$ to be $(p-1)$-th power saturated, it must contain an integer $n$ so that $$n\equiv x^{p-1}\bmod p.$$ However, by Fermat's Little Theorem, $x^{p-1}\in\{0,1\}\bmod p$, and no element of $S$ can be $0$ or $1$ modulo $p$, since all are less than $p$ and greater than $1$.

---

Here's a proof that $A_p=p+1$ for prime $p$.

Lemma. Let a subspace $V$ of $\mathbb{F}_p^k$ satisfy that, for each $1\leq i\leq k$, there exist some $x\in V$ for which $x_i\neq 0$. Then, as long as $k\leq p$, there exists some $x\in V$ so that $x_i\neq 0$ for each $1\leq i\leq k$.

Proof. We use the probabilistic method. Pick an $x\in V$ uniformly at random. For each $i$, since $\{y_i \colon y\in V\}$ is not $\{0\}$, the values $y_i$ range uniformly at random throughout $\mathbb{F}_p$, and so $$\operatorname{Pr}(x_i=0)=\frac1p.$$ As a result, $$\operatorname{Pr}(\text{any } x_i=0)\leq \sum_{i=1}^k \operatorname{Pr}(x_i=0)=\frac kp.$$ This is enough as long as $k<p$; if $k=p$, we only need the $\leq$ above to be strict. It is, since the zero vector is counted once on the left and $k$ times on the right.

---

Now, assume that $A_p\leq p$, so there exists a set $\{m_1,\dots,m_p\}$ of positive integers so that, for each prime $q$, some $m_i$ is a $p$-th power. Let $S$ be the set of all primes that divide $\prod m_i$, and associate with each $m_i$ a vector $v_i\in \mathbb{F}_p^S$ so that $(v_i)_r$ is the exponent of $r$ in the prime factorization of $m_i$, when taken modulo $r$.

We claim that there exists a vector $w$ so that $v_i\cdot w\neq 0$ for each $1\leq i\leq p$. Firstly, let $S'\subset S$ be a set of primes of size $\leq p$ so that, for each $i$, $(v_i)_r\neq 0$ for some $r\in S'$; such a prime $r\in S$ exists for each $i$ since no $m_i$ is a perfect $p$th power. We will set $w$ to be $0$ on $S\setminus S'$.

Now, we have $p$ vectors $v_1',\dots,v_p'$ in $\mathbb{F}_p^{S'}$. Let $V\subset \mathbb{F}_p^p$ consist of all vectors of the form $$\begin{bmatrix}v_1'\cdot w' \\ v_2'\cdot w' \\ \vdots \\v_p'\cdot w'\end{bmatrix}$$ for all $w'\in\left(\mathbb{F}_p^{S'}\right)^\vee.$ We see that for each $i$, since $v_i'$ is not the zero vector, there exists some $w'$ so that $v_i'\cdot w'$ is not $0$, and so $V$ satisfies the conditions of our lemma, whence we can find some $w'$ so that $v_i'\cdot w'\neq 0$ for all $i$, whence $v_i\cdot w \neq 0$ for all $i$, as desired.

Now, we find some large prime $q$ so that no $m_i$ is an $p$th power modulo $q$. We first pick $q$ to be $1\bmod p$ and define a morphism $f:\mathbb{F}_q^\times\to\mathbb{F}_p^+$ by sending some generator of the first to a generator of the second. In particular, under this map, $f(x)=0$ if and only if $x$ is a $p$th power modulo $q$.

We now wish that, for each $r\in S$, $f(r)=w_r$. If this is true, then $$f(m_i)=f\left(\prod_{r\in S}r^{\nu_r(m_i)}\right)=\sum_{r\in S}\nu_r(m_i)w_r=\sum_{r\in S}(v_i)_rw_r\neq 0,$$ as desired. So, we want, fixing some $p$th root of unity $\zeta$, for $$\left(\frac rq\right)_p=\zeta^w_r$$ for all $r\in S$ (using the power residue symbol). Eisenstein reciprocity tells us that this is the same as $$\left(\frac qr\right)_p = \zeta^w_r.$$ This is simply a condition on $q\bmod r$, so by the Chinese Remainder Theorem and Dirichlet's Theorem we can find some valid $q$.

(I'm not sure this final argument with Eisenstein reciprocity is completely right, but the general principle should work.)

---

For completeness' sake, I'll supply a proof that user760870's stated set works. Set $$S=\{2\}\cup\{3\cdot 2^i\colon 0\leq i\leq p-1\}$$ to be a set of $p$ positive integers. Assume none of them is a perfect $p$th power modulo some prime $q$, and note that $q\neq 2,3$. Let $g$ be a primitive root modulo $q$, let $h=g^{(q-1)/p}$, and let $k_2$ and $k_3$ be so that $g^{k_i}\equiv i\bmod q$. We have that none of $g^{ak_2+bk_3}$ is a perfect $p$th power modulo $q$ for $(a,b)=(1,0)$ or $b=1$; this implies that $$h^{ak_2+bk_3}\neq 1$$ for each of these $(a,b)$. In particular, $$ak_2+bk_3\not\equiv 0\bmod p$$ for any of these $(a,b)$. This means that $k_2\not\equiv 0\bmod p$, so the multiples of $k_2$ form a complete residue system $\bmod p$. This means that $ak_2\equiv -k_3$ for some $a$, a contradiction.