Problem 1698

1. Define the generating functions:
Let $f(x) = 1 + x + x^2$ and $F(x) = f(x) f(x^2) \cdots f(x^{p-1})$. Then, $F(x) = \sum_{n=0}^{p(p-1)} a_n x^n$, where $a_n$ is the number of $(p-1)$-tuples $(x_1, \ldots, x_{p-1})$ with $x_j \in \{0, 1, 2\}$ such that $x_1 + 2x_2 + \cdots + (p-1)x_{p-1} = n$.

2. **Count the tuples for $E(\{0,1,2\})$:**
The number $|E(\{0,1,2\})|$ is the sum of $a_n$ for $n$ divisible by $p$. Using roots of unity, let $\omega = e^{2\pi i / p}$. We know that:
$$1 + \omega^j + \omega^{2j} + \cdots + \omega^{(p-1)j} = \begin{cases} p & \text{if } p \mid j \\ 0 & \text{if } p \nmid j \end{cases}$$
Therefore, summing $F(x)$ for $x = 1, \omega, \omega^2, \ldots, \omega^{p-1}$:
$$F(1) + F(\omega) + \cdots + F(\omega^{p-1}) = p |E(\{0,1,2\})|$$
Notice that $F(1) = 3^{p-1}$. For $j \neq 0 \mod p$, $(1, \omega^j, \omega^{2j}, \ldots, \omega^{(p-1)j})$ is a permutation of $(1, \omega, \omega^2, \ldots, \omega^{p-1})$. Thus:
$$F(\omega) = F(\omega^2) = \cdots = F(\omega^{p-1}) = 1$$
Hence:
$$p |E(\{0,1,2\})| = 3^{p-1} + (p-1) \cdot 1$$
$$|E(\{0,1,2\})| = \frac{3^{p-1} + p - 1}{p}$$

3. **Count the tuples for $E(\{0,1,3\})$:**
Let $g(x) = 1 + x^2 + x^3$ and $G(x) = g(x) g(x^2) \cdots g(x^{p-1})$. Similarly, we have:
$$|E(\{0,1,3\})| = \frac{G(1) + (p-1)G(\omega)}{p}$$
$$G(1) = 3^{p-1}$$
We need to show that $1 \leq G(\omega)$ and equality holds only for $p = 5$.

4. **Analyze $G(\omega)$:**
Let $h(x) = x^3 + x + 1$. The roots of $h(x)$ are complex numbers $\lambda, \mu, \nu$ with $\lambda + \mu + \nu = 0$. We have:
$$G(\omega) = \prod_{j=1}^{p-1} (1 + \omega^j + \omega^{3j}) = \prod_{j=1}^{p-1} (\omega^j - \lambda)(\omega^j - \mu)(\omega^j - \nu)$$
Using the identity $\prod_{j=1}^{p-1} (x - \omega^j) = \frac{x^p - 1}{x - 1}$ for $x = \lambda, \mu, \nu$:
$$G(\omega) = \left( \frac{\lambda^p - 1}{\lambda - 1} \right) \left( \frac{\mu^p - 1}{\mu - 1} \right) \left( \frac{\nu^p - 1}{\nu - 1} \right)$$
Since $(\lambda - 1)(\mu - 1)(\nu - 1) = -h(1) = -3$, we have:
$$(\lambda^p - 1)(\mu^p - 1)(\nu^p - 1) = -3$$
Given $\lambda^3 + \lambda + 1 = 0$, for all natural numbers $k$, $\lambda^{k+3} + \lambda^{k+1} + \lambda^k = 0$. By induction, $\lambda^r + \mu^r + \nu^r \in \mathbb{Z}$.

5. **Show $G(\omega) \geq 1$:**
Assume $G(\omega) = 1$. Then:
$$(\lambda^p - 1)(\mu^p - 1)(\nu^p - 1) = -3$$
The roots $\lambda^p, \mu^p, \nu^p$ satisfy $m(x) = x^3 - qx^2 + (1+q)x + 1 = 0$ with $q = \lambda^p + \mu^p + \nu^p \in \mathbb{Z}$. Since $\lambda$ is the real root of $x^3 + x + 1 = 0$ and $-1 < \lambda < -\frac{1}{2}$, if $q < 0$, then $m(\lambda^p) \neq 0$, leading to a contradiction. Thus, $1 \leq q$.

6. **Special case for $p = 5$:**
For $p = 5$, $g(\omega) = 1 + \omega + \omega^2 = -\omega^2(1 + \omega^2)$, and:
$$G(\omega) = \prod_{j=1}^{p-1} (1 + \omega^{2j}) = \prod_{j=1}^{p-1} (1 + \omega^j) = \frac{1 - (-1)^p}{1 - (-1)} = 1$$
Therefore:
$$|E(\{0,1,3\})| = \frac{3^{p-1} + (p-1)G(\omega)}{p} = \frac{3^{p-1} + p - 1}{p}$$
Hence, $|E(\{0,1,3\})| = |E(\{0,1,2\})|$ for $p = 5$.

7. Conclusion:
For $p > 3$, $|E(\{0,1,3\})| \geq |E(\{0,1,2\})|$ with equality if and only if $p = 5$.

$\blacksquare$