2 Finding solutions of additive systems with distinct entries

Our basic parameter, P, is always assumed to be a large positive integer. Whenever $\varepsilon $ appears in a statement, either implicitly or explicitly, we assert that the statement holds for every $\varepsilon>0$ . Implicit constants in Vinogradov’s notation $\ll $ and $\gg $ may depend on $\varepsilon $ , r, s, k, K and the elements of the matrix C.

Let $C =[{\mathbf c}_1,\ldots ,{\mathbf c}_s]= (c_{i,j})_{\substack {1 \leqslant i \leqslant r \\ 1 \leqslant j \leqslant s}} \in {\mathbb Z}^{r \times s}$ be given, and consider the diagonal system

(2.1) $$ \begin{align} \sum_{1 \leqslant j \leqslant s}c_{i,j}x_j^k = 0, \quad 1 \leqslant i \leqslant r. \end{align} $$

We define $S_k(P;C)$ to be the set of solutions ${\mathbf x} \in {\mathbb Z}^s$ to (2.1), where $\max _{j}|x_j| \leqslant P$ . Given $i, j$ with $1 \leqslant i< j \leqslant s$ , it is not difficult to see that

where $C^{(i,j)}$ is the matrix obtained by substituting the ith column of C with ${\mathbf c}_{i}+{\mathbf c}_{j}$ and deleting the jth column of C.

Thus, if $S^*_k(P;C)$ denotes the subset of $S_k(P;C)$ with distinct entries,

(2.2)

Separately, one may deduce from [Reference Flores5, Lemma 3.4] and [Reference Low, Pitman and Wolff6, Lemma 1] the following result.

Lemma 2.1. Let $K \geqslant 2$ and $C \in {\mathbb Z}^{r \times s}$ with $s \geqslant rK(K+1)$ . If C contains a partitionable submatrix of size $r \times rK(K+1)$ , then one has the bound

for any $\varepsilon> 0$ .

If C dominates the function

$$ \begin{align*}\frac{x-r\{(s-2)/r\}}{ \lfloor (s-2)/2 \rfloor},\end{align*} $$

then, for $1 \leqslant i <j \leqslant s$ , the matrix $C^{(i,j)}$ contains a submatrix of C of size $r \times (s-2)$ . By [Reference Low, Pitman and Wolff6, Lemma 1], this matrix contains a partitionable submatrix of size $r \times r \lfloor {(s-2)}/{r} \rfloor .$ Combining this with (2.2), Lemma 2.1 and [Reference Flores5, Theorem 2.2], we deduce the following general result.

Lemma 2.2. Let $K \geqslant 2$ and suppose that $C \in {\mathbb Z}^{r \times s}$ satisfies $s \geqslant rK(K+1)+2$ . If C dominates the function

$$ \begin{align*}F(x) = \max\bigg\{ \frac{x- r\{s/r\}}{ \lfloor s/r \rfloor}, \frac{x- r\{(s-1)/r\}}{ \lfloor (s-1)/r \rfloor}, \frac{x- r\{(s-2)/r\}}{ \lfloor (s-2)/r \rfloor} \bigg\},\end{align*} $$

then

where $\sigma _K(C) \geqslant 0$ is a real number depending only on K and C. Additionally, ${\sigma _K(C)> 0}$ if there exist nonsingular real and p-adic simultaneous solutions to the system (2.1) for $1 \leqslant k \leqslant K$ .

3 K-multimagic squares with distinct entries

A matrix ${\mathbf Z} = (z_{i,j})_{\substack {1 \leqslant i,j \leqslant N}}$ is an $\textbf {MMS}(K,N)$ if and only if, for all k with $1 \leqslant k \leqslant K$ , it satisfies the simultaneous conditions

(3.1) $$ \begin{align} \sum_{1 \leqslant i \leqslant N} z_{i,j}^{k} = \sum_{1 \leqslant i \leqslant N} z_{i,i}^{k} \quad \text{for } 1 \leqslant j \leqslant N, \end{align} $$

(3.2) $$ \begin{align} \sum_{1 \leqslant j \leqslant N} z_{i,j}^{k} = \sum_{1 \leqslant j \leqslant N} z_{j,N-j+1}^{k} \quad \text{for } 1 \leqslant i \leqslant N. \end{align} $$

One may wonder if these equations are equivalent to those of an $\textbf {MMS}(K,N)$ . Indeed, at a first glance, it does not seem clear that the main diagonal and anti-diagonal are equal. One can show that this is implied by simply summing over all j in (3.1) and noting that this is equal to summing over all i in (3.2). Upon dividing out a factor of N, one deduces that (3.1) and (3.2) imply

$$ \begin{align*}\sum_{1 \leqslant i \leqslant N} z_{i,i}^{k} = \sum_{1 \leqslant j \leqslant N} z_{j,N-j+1}^{k}.\end{align*} $$

Before we construct a matrix corresponding to this system, we must first establish some notational shorthand. Let $\mathbf {1}_n$ denote an n-dimensional vector of all ones and $\mathbf {0}_n$ an n-dimensional vector of all zeros. Let ${\mathbf e}_n(m)$ denote the mth standard basis vector of dimension n. For a fixed N, we define

$$ \begin{align*}D_1(N) = \{(i,j) \in ([1,N] \cap {\mathbb Z})^2: i = j\}\end{align*} $$

and

$$ \begin{align*}D_2(N) = \{(i,j) \in ([1,N] \cap {\mathbb Z})^2: i +j = N+1\}.\end{align*} $$

For each $(i,j) \in ([1,N] \cap {\mathbb Z})^2$ , we define the $2N$ -dimensional vectors

$$ \begin{align*}{\mathbf d}_{i,j} = \begin{cases} ({\mathbf e}_N(i)-\mathbf{1_N},{\mathbf e}_N(j) - \mathbf{1_N}) & \mbox{for } (i,j) \in D_1(N) \cap D_2(N), \\ ({\mathbf e}_N(i)-\mathbf{1_N},{\mathbf e}_N(j)) & \mbox{for } (i,j) \in D_1(N) \backslash D_2(N), \\ ({\mathbf e}_N(i),{\mathbf e}_N(j) - \mathbf{1_N}) & \mbox{for } (i,j) \in D_2(N) \backslash D_1(N), \\ ({\mathbf e}_N(i),{\mathbf e}_N(j)) & \text{otherwise.} \\ \end{cases}\end{align*} $$

Let $\phi : [1,N^2] \cap {\mathbb Z} \to ([1,N] \cap {\mathbb Z})^2$ be any fixed bijection. Then, the $2N \times N^2$ matrix,

$$ \begin{align*}C^{\text{magic}}_{N} = C^{\text{magic}}_{N}(\phi) = [{\mathbf d}_{\phi(1)},\ldots,{\mathbf d}_{\phi(N^2)}],\end{align*} $$

corresponds to the system defined by (3.1) and (3.2) up to some arbitrary relabelling of variables defined by the bijection $\phi $ . We now establish that one may apply Lemma 2.2 with $C=C_N^{\text {magic}}$ .

Lemma 3.1. For $N \geqslant 4$ , the matrix $C_N^{\mathrm {\scriptsize magic}}$ dominates the function

$$ \begin{align*}F(x) = \max\bigg\{ \frac{x- r\{s/r\}}{ \lfloor s/r \rfloor}, \frac{x- r\{(s-1)/r\}}{ \lfloor (s-1)/r \rfloor}, \frac{x- r\{(s-2)/r\}}{ \lfloor (s-2)/r \rfloor} \bigg\},\end{align*} $$

with $s = N^2$ and $r=2N$ .

Proof. We show in [Reference Flores5, Section 4] that $C_N^{\text {magic}}$ satisfies the rank condition

$$ \begin{align*}\text{rank} \,((C_N^{\text{magic}})_J) \geqslant \begin{cases} \lceil 2 \sqrt{|J|} \rceil-1 & \text{if }1 \leqslant |J| \leqslant N(N-1)-1, \\ |J|-N^2+3N-1 & \text{if }N(N-1)-1 \leqslant |J| \leqslant N(N-1)+1, \\ 2N & \text{if }N(N-1)+1 \leqslant |J| \leqslant N^2, \end{cases} \end{align*} $$

when $|J| \neq (N-1)^2+1$ and

$$ \begin{align*} \text{rank} \,((C_N^{\text{magic}})_J) \geqslant 2N-3,\end{align*} $$

when $|J|= (N-1)^2+1$ . Given this, if $|J|> N(N-1)$ , trivially,

$$ \begin{align*}\min\{F(|J|),2N\} = 2N \leqslant \text{rank} \,((C_N^{\text{magic}})_J).\end{align*} $$

Let us now focus on the case in which N is even and $|J| \leqslant N(N-1)$ . When N is even, one may show that

$$ \begin{align*}F(x) = \begin{cases} \dfrac{2x}{N} & \text{if}\ 0 \leqslant x \leqslant N(N-1), \\[6pt] \dfrac{2x-4}{N-2}-4 & \text{if}\ N(N-1) \leqslant x. \end{cases}\end{align*} $$

Thus, if $N(N-1)-1 \leqslant |J| \leqslant N(N-1)$ ,

$$ \begin{align*}\min\{F(|J|),2N\} = \frac{2|J|}{N} \leqslant |J| - N^2+3N-1 \leqslant \text{rank} \,((C_N^{\text{magic}})_J).\end{align*} $$

Let us now suppose that $1 \leqslant |J| < N(N-1)-1$ and $|J| \neq (N-1)^2+1$ . Similarly, in this range,

$$ \begin{align*}\min\{F(|J|),2N\}= \frac{2|J|}{N} \leqslant \big\lceil{2 \sqrt{|J|}\,\big\rceil}-1 \leqslant \text{rank} \,((C_N^{\text{magic}})_J).\end{align*} $$

Let us now consider the case $|J| = (N-1)^2+1$ . Since $N \geqslant 4$ ,

$$ \begin{align*}\min\{F(|J|),2N\} = 2N-4+4/N \leqslant 2N-3 \leqslant \text{rank} \,((C_N^{\text{magic}})_J).\end{align*} $$

The case in which N is odd may be established in a similar fashion.

By Lemma 2.2 and using the existence of nonsingular solutions to the magic square system proved in [Reference Flores5], we deduce the following asymptotic formula.

Theorem 3.2. For $K \geqslant 2$ and $N> 2K(K+1)$ , let $M^*_{K,N}(P)$ denote the number of MMS $(K,N)$ consisting of $N^2$ distinct integers bounded in absolute value by P. Then, there exists a constant $c> 0$ for which one has the asymptotic formula

$$ \begin{align*}M^*_{K,N}(P) \sim cP^{N(N-K(K+1))}.\end{align*} $$

This immediately implies Theorem 1.3.

4 Magic squares of distinct kth powers

Let us now consider the problem of showing the existence of magic squares of distinct kth powers. One may repeat the arguments of Rome and Yamagishi [Reference Rome and Yamagishi7], where instead of requiring a lower bound on the size of the largest partitionable submatrix, we assume that the matrix of coefficients dominates the function

$$ \begin{align*}F(x) = \max\bigg\{ \frac{x- r\{s/r\}}{ \lfloor s/r \rfloor}, \frac{x- r\{(s-1)/r\}}{ \lfloor (s-1)/r \rfloor}, \frac{x- r\{(s-2)/r\}}{ \lfloor (s-2)/r \rfloor} \bigg\}.\end{align*} $$

It is clear that all arguments of [Reference Rome and Yamagishi7] follow from this assumption by [Reference Low, Pitman and Wolff6, Lemma 1], assuming $ \lfloor {(s-2)}/{r} \rfloor $ is large enough in terms of k. How large this term needs to be, as seen in Lemma 2.1, is directly determined by when one can establish a mean value estimate of the type

where A is the set from which the solutions may come. Then, by a direct analogue of the arguments in Section 2, we obtain a version of [Reference Rome and Yamagishi7, Theorem 1.4] which provides an asymptotic for the number of solutions with distinct entries.

Lemma 4.1. Let $k \geqslant 2$ and $C \in {\mathbb Z}^{r \times s}$ , where $s \geqslant r \min \{2^{k},k(k+1)\} +2$ . If C dominates the function

$$ \begin{align*}F(x) = \max\bigg\{ \frac{x- r\{s/r\}}{ \lfloor s/r \rfloor}, \frac{x- r\{(s-1)/r\}}{ \lfloor (s-1)/r \rfloor}, \frac{x- r\{(s-2)/r\}}{ \lfloor (s-2)/r \rfloor} \bigg\},\end{align*} $$

then

where $\sigma _k(C) \geqslant 0$ is a real number depending only on k and C. Additionally, $\sigma _k(C)> 0$ if there exist nonsingular real and p-adic solutions to the system (2.1).

Let

$$ \begin{align*} \mathscr{A}(Q) = \{{\mathbf x} \in {\mathbb Z}^s: \text{prime } p \mid x_i \text{ for any}\ i\ \text{with}\ 1 \leqslant i \leqslant s, \text{implies}\ p \leqslant Q\}.\end{align*} $$

Then, the same may be done to obtain an analogue of [Reference Rome and Yamagishi7, Theorem 1.5], which provides an asymptotic for the number of smooth solutions with distinct entries.

Lemma 4.2. Let $k \geqslant 2$ and $C \in {\mathbb Z}^{r \times s}$ , where $s \geqslant r \lceil k(\log k + 4.20032) \rceil +2$ . If C dominates the function

$$ \begin{align*}F(x) = \max\bigg\{ \frac{x- r\{s/r\}}{ \lfloor s/r \rfloor}, \frac{x- r\{(s-1)/r\}}{ \lfloor (s-1)/r \rfloor}, \frac{x- r\{(s-2)/r\}}{ \lfloor (s-2)/r \rfloor} \bigg\},\end{align*} $$

then, providing $\eta>0$ is sufficiently small in terms of $s,r,k$ and C,

where $\sigma _k(C)$ is the same quantity as in Lemma 4.1 and $c(\eta )>0$ depends only on $\eta $ .

Applying Lemmas 4.1 and 4.2 with $C = C_N^{\text {magic}}$ and noting that the analysis in [Reference Flores5, Section 5] implies $\sigma _k(C_N^{\text {magic}})$ is positive, we deduce Theorem 1.5.