Minimizing...

A friend asked me this math question (presumably popped out of QFT or something)

Consider a set of N elements: {a_i}
It is known that sum(a_i) = 0
and that sum(a_i²) = 1
What is the minimum of sum(a_i⁴)?

The AM-RMS/power mean inequality tells us that sqrt(sum(a_i⁴)/N) >= sum(a_i²)/N ->
sum(a_i⁴) >= 1/N, with equality iff the a_is are the same.

If N is even, then the a_is just alternate as +-1/sqrt(N)
If N is odd, then that trick doesn't work, since then the sum won't = 0.  Therein lies the problem.  It seems likely that the answer has (N+1)/2 of the a_is equaling one number, and the remainder equaling something else.  However, I haven't been able to prove that this is the optimal solution yet.
I tried brute forcing this for N=3, but after an hr of algebra... the answer is always 1/2, regardless of how I pick the a_is.

idunno bro
u wanna play sum halo?

I dunno lol, this is trickier than it looks.  I think Lagrange multipliers are probably the thing to try, but I hate calculus so I cba to work it out atm :P.  Here's what I get numerically in mathematica:


n  | min
--------------------------------------------------------------------
2  | 0.49999999999999999999999998707530292885894258013424 = 1/2
3  | 0.49999999999999999999999998707530292885894258013424 = 1/2
4  | 0.24999999999999999999999998707530292885894258013425 = 1/4
5  | 0.23333333333333333333333332207448610691712331425027 = 7/30
6  | 0.16666666666666666666666666092235685727064114672633 = 1/6
7  | 0.15476190476190476190476189980890293645614806358886 = 13/84
8  | 0.15833333333333333333333332814909373035342030158718 = 19/120 (should be 1/8)
9  | 0.11666666666666666666666665540781944025045664758361 = 7/60
10 | 0.09999999999999999999999999172819387446972325128590 = 1/10
11 | 0.09393939393939393939393938663984785433003126215405 = 31/330
12 | 0.08333333333333333333333332758902352393730781339299 = 1/12
13 | 0.07875457875457875457875457362416994522082621919912 = 43/546
14 | 0.07142857142857142857142856720826218085189961800301 = 1/14
15 | 0.06785714285714285714285713904831376107598226239058 = 19/280
16 | 0.06646825396825396825396825031374621111412151941437 = 67/1008 (should be 1/16)
17 | 0.05964052287581699346405228463942455072362360671260 = 73/1224
18 | 0.05555555555555555555555555300252897360176643558207 = 1/18
19 | 0.05321637426900584795321637192644483685522992523848 = 91/1710
20 | 0.04999999999999999999999999793204846861743081282147 = 1/20


f[p_, n_] := Sum[x[i]^p, {i, n}]
g[n_] := NMinimize[{f[4, n], f[1, n] == 0, f[2, n] == 1}, Array[x, n], WorkingPrecision -> 50][[1]]

The function NMinimize[] is unreliable (the answers for 8 and 16 are wrong at least), but the exact function Minimize[] is too slow to use. I could only double-check up to N=7, but no further.  The rest of the even ones are correct anyway.  It's interesting that they all seem to be rational, though.

>>1
For



, I get


, the results of which seems to match >>3 (Well, I only tested it for n=5...).
I haven't proved it's optimal, but I think it's the best real solution at least.
Does your function try complex numbers, >>3?

>>4
The rest of them check out as well, so it looks like that's it.

If you want complex solutions, you have to specify wha exactly you're minimizing, since the sum will be complex in general.

Since I haet subscripts, let the numbers be a,b,c,\ldots.  Define the Lagrangian as

\Lambda(a,b,c,...,\lambda_1, \lambda_2) = (a^4 + b^4 + c^4 + \cdots) - \lambda_1 (a+b+c+\cdots) - \lambda_2 (a^2 + b^2 + c^2 + \cdots - 1)

Setting the partials with respect to a,b,c,\ldots to zero gives

4a^3 - \lambda_1 - 2\lambda_2 a = 0
4b^3 - \lambda_1 - 2\lambda_2 b = 0
4c^3 - \lambda_1 - 2\lambda_2 c = 0
...

Therefore each number a,b,c,\ldots is a root of the cubic equation f(x) = 4x^3 - \lambda_1 - 2\lambda_2 x = 0.  This shows there are at most three distinct numbers among the a,b,c,\ldots in an optimal solution.

Assume that there are exactly three distinct numbers, a,b,c, and let their multiplicities be s,t,(n-s-t) respectively.  By looking at coefficients of the cubic f(x) = 4x^3 - \lambda_1 - 2\lambda_2 x = 0, we can see that

a + b + c = 0
ab+bc+ca = -\lambda_2 / 2
a^2+b^2+c^2 = (a+b+c)^2 - 2(ab+bc+ca) = \lambda_2

-\lambda_2/2 = ab+bc+ca = ab+c(a+b) = ab+(-a-b)(a+b) = -a^2-ab-b^2
\lambda_2 = 2(a^2+ab+b^2) = 2(b^2+bc+c^2) = 2(c^2+ca+a^2)

and by looking at the original problem, we have

sa + tb + (n-s-t)c = 0
sa^2 + tb^2 + (n-s-t)c^2 = 1

We're going to use this to get expressions for a^2, b^2, c^2 similar to what >>4 did. 

Now subtract

(n-s-t)(a+b+c)=0

from the first of these last two equations and

(n-s-t)(a^2+b^2+c^2)=(n-s-t)\lambda_2 = (n-s-t)(2a^2+2ab+2b^2)

from the second, to get

(2s+t-n)a + (2t+s-n)b = 0
(2s+t-n)a + (2t+s-n)b = 1-(n-s-t)(2a^2+2ab+2b^2)

Solving for b in the first of these and subbing into the second, then solving the second for a^2 (all in Maple), gives

{a}^{2}={\frac { \left( -2t+n-s \right) ^{2}}{ \left( s+t \right) {n
}^{2}+ \left( -{s}^{2}-{t}^{2}-10ts \right) n+9st \left( s+t
 \right) }}

Similarly, we find

{b}^{2}={\frac { \left( -2s+n-t \right) ^{2}}{ \left( s+t \right) {n
}^{2}+ \left( -{s}^{2}-{t}^{2}-10ts \right) n+9\,st \left( s+t
 \right) }}

{c}^{2}={\frac { \left( -t+s \right) ^{2}}{ \left( 9t-n \right) {s}^
{2}+ \left( n-t \right)  \left( n-9t \right) s+nt \left( n-t
 \right) }}

And finally, from this we get (all in Maple)

sa^4 + tb^4 + (n-s-t)c^4 = {\frac {{n}^{2}-3ns-3tn+3{s}^{2}+3ts+3{t}^{2}}{9s{t}^{2}+9t{s}^{2}+s{n}^{2}-n{s}^{2}-n{t}^{2}+t{n}^{2}-10stn}}

Denote the RHS of this as M(s,t).  With Maple again, we find that

M_s (s,t) = -{\frac { \left( n-3t \right) ^{3} \left( -2s+n-t \right) }{
 \left( 9s{t}^{2}+9t{s}^{2}+s{n}^{2}-n{s}^{2}-n{t}^{2}+t{n}^{2}-10stn \right) ^{2}}}

M_t (s,t) = -{\frac { \left( n-3s \right) ^{3} \left( -2t+n-s \right) }{ \left( 9s{t}^{2}+9t{s}^{2}+s{n}^{2}-n{s}^{2}-n{t}^{2}+t{n}^{2}-10stn \right) ^{2}}}

You can see both partials are zero iff t = s = n/3, which gives m(s,t) = 3/2n, but I think this is a saddle point or something.  I forget how to check that.

For the boundaries, we're looking at the region bounded by s=0, t=0, s+t=n, and if you go through and check it, the minimums occur at s=0, t=n/2, s=n/2, t=0, and s=n/2, t=n/2.  So the minimum happens when there are actually only two distinct values, and each occurs the same amount of times.  In the case that n is odd, the next best thing is to let s=(n-1)/2, t=(n+1)/2, u=0, and you end up with the formula >>4 has as your best possible answer.

So in the end, the best possible is  1/n for n even, and \frac{n^2+3}{n^3-n} for n odd.

>>3
>>4
>>5
In other news, PARI's algdep() function for recognizing fractions in decimal form works like a charm. ^_^

>>6
Thanks.  I wasn't expecting Lagrange multipliers to pop up here (mostly because I'm rusty with its use).  I think checking for saddle points requires 2nd derivatives, which would complicate the question unnecessarily.

I tried plotting M(s,t) for n=5, and it seems like s=t=n/3 is a genuine local minimum... completely enclosed by poles.  However, there does seem to be a saddle point ~ s=t=1/2.  I'll look more into it.  Thanks again.

How are you guys using tex?  Just testing: \Delta^o?

>>10
Oh fuck yeah okay.

>Consider a set

stopped reading there

>>12
What's wrong with sets?

>>13
They're beyond his ability to comprehend.