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$.



On permuted sum of squares of primes in a list
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$). 


