6
$\begingroup$

We want to pick a set of distinct primes (if not possible, then just positive numbers) $p_1,p_2,\dots,p_k$ such that there exists $t$ permutations, $\sigma_1(\cdot)$,$\sigma_2(\cdot),\dots,\sigma_t(\cdot)$, of the primes such that the sum of vectors $$(p_1^2,p_2^2,\dots,p_k^2)+(p_{\sigma_1(1)}^2,p_{\sigma_1(2)}^2,\dots,p_{\sigma_1(k)}^2)+\dots+(p_{\sigma_t(1)}^2,p_{\sigma_t(2)}^2,\dots,p_{\sigma_t(k)}^2)=(T,T,T,....,T)$$ where $T=O(k^c)$ for some constant $c > 0$.

Is this possible and how do you do this? Given a $k$, can $t$ be as small as $O(\log(k))$?

For every $k$ is there a polynomially big $T$ and a $t$ that is logarithmic in $k$?

From Gerry's comments: let us fix $t=2$, for every $k$, is there a $T$ that is polynomial in $k$ that satisfies the above relations? His comments provide existence of values of $k$ such that $T=k$ but does not cover all $k$.

$\endgroup$
17
  • 1
    $\begingroup$ See oeis.org/A088919 for Smallest number having exactly $n$ representations as sum of two squares of distinct primes. $\endgroup$ Sep 17, 2013 at 23:44
  • 1
    $\begingroup$ For $t=3$ (and $k$ divisible by 3), all you need is numbers with a lot of representations as sums of three squares (of distinct primes). And so on. $\endgroup$ Sep 17, 2013 at 23:50
  • 1
    $\begingroup$ I don't know the answer to the primes questions, since I don't know what's known about numbers that are the sum of squares of $k$ distinct primes in many ways --- but I bet the analytic number theorists have answers. $\endgroup$ Sep 17, 2013 at 23:54
  • 1
    $\begingroup$ Sorry, I'm not that familiar with the literature. "Hardy-Littlewood circle method" and "sieve methods" may be applicable. $\endgroup$ Sep 18, 2013 at 0:03
  • 2
    $\begingroup$ Consider sums of three squares of primes that are all between $X$ and $2X$. Counted with multiplicity there are $\gg X^3/(\log X)^3$ such sums. They all lie below $12X^2$. Therefore some integer must be represented very many times. $\endgroup$
    – Lucia
    Sep 18, 2013 at 0:12

1 Answer 1

6
$\begingroup$

For large $k$ it is always possible to do this with $30$ permutations. Write $k$ as $30a+6b+5c$ where $0\le b\le 4$ and $0\le c\le 5$. Then the permutations will be a product of $a$ disjoint $30$-cycles, $b$ disjoint $6$-cycles, and $c$ disjoint $5$ cycles (take a cycle consisting of the first thirty primes, then the next thirty primes etc until we get to the last five primes). The resulting permutation has order thirty and its powers are the thirty permutations we want. (The basic idea here is what was expressed in Gerry Myerson's comments to the question. Myerson's observation is that when $k$ is a multiple of $3$, one can use products of three cycles, and three permutations suffice. In general this would allow one to take the smallest prime dividing $k$ as a possible answer. What is covered here is all the cases when $k$ does not have a small prime factor.)

For the sums to add up to the same number, we must find a number $N$ such that $30N$ is expressible as the sum of thirty squares of distinct primes in at least $a$ ways; $6N$ is expressible as the sum of six squares of distinct primes in at least $b$ ways; and $5N$ is expressible as the sum of five squares of distinct primes in at least $5$ ways. This can be arranged thanks to the Hardy-Littlewood circle method.

It may not be easy to find an exact reference that does so however. So here's a little context. It is an old conjecture that every integer that is $4 \pmod {24}$ is the sum of four squares of primes. This remains difficult to prove. However Hua showed in 1938 that every large integer that is $5 \pmod{24}$ may be written as a sum of five squares of primes. In his argument, which is based on the circle method, it would be possible to arrange for the primes to be distinct, and to guarantee many solutions. In fact for five squares of primes (assuming the congruence condition $\pmod {24}$) there will be about $n^{3/2-\epsilon}$ representations of a large number $n$. Note that representations where a prime is repeated, or representations with a given prime will be at most $O(n^{1+\epsilon})$ in number. So one can guarantee many representations ($n^{1/2-\epsilon}$ at least) as a sum of five squares of distinct primes, and no primes shared among two such solutions. Once one has the result for five squares, of course every integer that is $j \pmod{24}$ for $j\ge 5$ may be expressed in many ways as a sum of $j$ squares of distinct primes. That finishes the job.

This problem seems a little strange to me; I would appreciate some motivation of where it came from.

Update: Actually I can give a reference that will work. It is work of Harman and Kumchev: see http://arxiv.org/pdf/0902.4190.pdf . Harman and Kumchev show that with very few exceptions, any number that is $3\pmod {24}$ and not a multiple of $5$ can be expressed as a sum of three squares of primes in $\gg n^{1/2-\epsilon}$ ways. Note that one doesn't have to worry about Siegel zeros, as this is an almost all result. From this and the argument above one can get that $12$ permutations suffice (writing $k=12 a +4b+3c$).

$\endgroup$
12
  • $\begingroup$ Be careful: we need not just distinct primes in each representation, but plenty of representations sharing no common primes. The first is not hard even without Hua's theorem, but I've never seen the second. Formally it is even impossible in the way you state it: if the number is even, every representation as a sum of squares of 5 primes should include 2... $\endgroup$
    – fedja
    Sep 29, 2013 at 12:17
  • $\begingroup$ I do not see the connection here. Could you put down your thoughts algebraically and symbolically as in the question? $\endgroup$
    – Turbo
    Sep 29, 2013 at 13:29
  • $\begingroup$ @fedja Please note that Hua's theorem takes $n$ to be $5 \pmod {24}$ and that every prime square apart from $4$ and $9$ is $1 \pmod {24}$. As for the number of representations, this is why I wrote that a reference would be hard to find, but the number of representations will be very many --- about $n^{3/2+o(1)}$ for five squares of distinct primes. $\endgroup$
    – Lucia
    Sep 29, 2013 at 13:43
  • $\begingroup$ @JAS Here's an example if that helps of the proof. Suppose $k=41=30+6+5$. Then take the permutation $(1,2,...,30)(31,...,36)(37,...41)$ and its powers. These give $30$ permutations of the primes $p_1$ to $p_{41}$. If you add the vectors, the first thirty entries will match and they are the number $30N$ written as a sum of $30$ squares of distinct primes (assume all primes $\ge 5$ so the squares are $1\pmod{24}$). Next six entries will be $5$ times a number that is a sum of six squares; and the last $5$ entries will be $6$ times a sum of $5$ squares.This is why we also want $5N$ and $6N$. $\endgroup$
    – Lucia
    Sep 29, 2013 at 14:00
  • 1
    $\begingroup$ To JAS: The solutions will be small. You need essentially an integer having about $k$ solutions as a sum of thirty squares of primes. This will be polynomial in $k$. See my remarks on the number of solutions in Hua's theorem -- there are lots of ways of writing numbers as sums of squares of (sufficiently many) primes. $\endgroup$
    – Lucia
    Sep 29, 2013 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.