April 2022

Xyzzy · 2022-04-02, 12:24

https://research.ibm.com/haifa/ponde...April2022.html

Kebbaj · 2022-04-04, 01:44

For trying n=4
I get this optimal solution:

x = [0.825694, -0.0756939 , -0.5 , -0.25]
y = [-0.0756939, -0.25, -0.5 , 0.825694]

f(x,y)= 6.74306

Can anyone confirm if there is other optimal results for n=4 ?

uau · 2022-04-04, 02:20

Quote:

Originally Posted by Kebbaj

I get this optimal solution:

Why do you call that "optimal"? It does not meet the criterion.

Kebbaj · 2022-04-04, 02:38

Quote:

Originally Posted by uau

Why do you call that "optimal"? It does not meet the criterion.

Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?

uau · 2022-04-04, 03:27

Quote:

Originally Posted by Kebbaj

Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?

You're wrong.

tgan · 2022-04-04, 07:55

Quote:

Originally Posted by Kebbaj

Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?

Reda i checked your Solution for n = 4 and getting the same results as you.
i did not search for optimal just checked that per my understanding it meets the constraints and calculate f(x,y)

Dieter · 2022-05-29, 12:16

Did anyone else find the excellent solution of Anders Kaseorg?
How do you find something like that?

uau · 2022-06-04, 19:54

Note that you can permute the order of x_i arbitrarily if you also permute y_i the same way.
Take the example solution given in the problem statement and order the x_i in ascending order:

x = [-0.3688259, -0.36163773, -0.3562014, 0.45420977, 0.63245526]
y = [-0.05259805, -0.04540969, -0.03997346, 0.77043701, -0.6324558]

Note that the last element in each is about the negative of the other.
Also,
y-x = [ 0.31622785, 0.31622804, 0.31622794, 0.31622724, -1.26491106]
except for the last element, y is about x plus a constant.

Now if we assume these features (except for last, y_i = x_i + c; y_last = -x_last) hold for solutions, what do they imply together with the general problem requirements?

The general problem requirements say x.x=1, y.y=1, sum(x)=0, sum(y)=0, x.y=0.

Since sum(x)=sum(y)=0, the changes to last and other elements from x to y must also sum to 0.
c*(n-1) - 2*x_last = 0. So c = x_last * 2/(n-1). (In the example case, 0.316 = 0.632 * 2/4).

sum(x)=0 implies x.[c,c,c,c,c]=0. Thus x.(x+c)=x.x=1. y=x+c except for last element, and x.y must be 0. Thus changing the last element from x_last+c=x_last*(n+1)/(n-1) to -x_last must change the dot product from 1 to 0. Thus x_last*x_last*(n+1)/(n-1) = x_last*(-x_last)+1, and x_last = sqrt((n-1)/(2n)). (In the example, 0.632 = sqrt(4/10)).

So this limits the values of n for which such rational solutions can exist to those for which (n-1)/(2n) is a square. Up to a million such values are 1, 2, 9, 50, 289, 1682, 9801, 57122, 332929.

It turns out that these are actually sufficient requirements to make a solution optimal. ANY x which fulfills sum(x)=0, x.x=1, x_last=sqrt(n-1)/(2n)) gives a solution by setting y=x+c except y_last.

To find an optimal solution of say length 50, it's now enough to find a vector of length 50 which fulfills these conditions:

sum(x)=0
x_last = sqrt(49/100) = 7/10
x.x = 1

(7/10)^2 = 49/100, so we need to fill the remaining elements of x with values that have these properties: they sum to -7/10, and their squares sum to 51/100. We'll just take -7/10, which leaves sum 0 and square-sum 2/100, and then add -1/10 and 1/10 which doesn't alter sum and fills square sum. (The published solution from Anders Kaseorg is one special case of constructing some values that have the required sum and sum of squares, but there are lots of other possibilities.)

So now we have
x=[-7/10, -1/10, 1/10, 0, 0, ..., 7/10]

and y=x+c, where c=x_last * 2/(n-1)=7/245, except last element.

y = [-7/10+7/245, -1/10+7/245, 1/10+7/245, 7/245, 7/245, ..., -7/10]

You can verify that these give a rational solution of length 50, which is valid (x.x=y.y=1, sum(x)=sum(y)=0, x.y=0), and fulfills the optimality condition f(x,y)=4.

2022-04-02, 12:24	#1
Xyzzy Aug 2002 3²×23×41 Posts	April 2022 https://research.ibm.com/haifa/ponde...April2022.html

2022-04-04, 01:44	#2
Kebbaj "Kebbaj Reda" May 2018 Casablanca, Morocco 63₁₆ Posts	For trying n=4 I get this optimal solution: x = [0.825694, -0.0756939 , -0.5 , -0.25] y = [-0.0756939, -0.25, -0.5 , 0.825694] f(x,y)= 6.74306 Can anyone confirm if there is other optimal results for n=4 ? Last fiddled with by Kebbaj on 2022-04-04 at 02:09

2022-05-29, 12:16	#7
Dieter Oct 2017 2×3²×7 Posts	April 2022 Did anyone else find the excellent solution of Anders Kaseorg? How do you find something like that?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
2022 project goals	gd_barnes	Conjectures 'R Us	5	2022-07-18 04:01
February 2022	tgan	Puzzles	21	2022-03-23 21:59
March 2022	Xyzzy	Puzzles	7	2022-03-21 10:45
January 2022	Xyzzy	Puzzles	25	2022-02-14 01:08

2022-06-04, 19:54	#8
uau Jan 2017 149 Posts	Note that you can permute the order of x_i arbitrarily if you also permute y_i the same way. Take the example solution given in the problem statement and order the x_i in ascending order: x = [-0.3688259, -0.36163773, -0.3562014, 0.45420977, 0.63245526] y = [-0.05259805, -0.04540969, -0.03997346, 0.77043701, -0.6324558] Note that the last element in each is about the negative of the other. Also, y-x = [ 0.31622785, 0.31622804, 0.31622794, 0.31622724, -1.26491106] except for the last element, y is about x plus a constant. Now if we assume these features (except for last, y_i = x_i + c; y_last = -x_last) hold for solutions, what do they imply together with the general problem requirements? The general problem requirements say x.x=1, y.y=1, sum(x)=0, sum(y)=0, x.y=0. Since sum(x)=sum(y)=0, the changes to last and other elements from x to y must also sum to 0. c(n-1) - 2x_last = 0. So c = x_last * 2/(n-1). (In the example case, 0.316 = 0.632 * 2/4). sum(x)=0 implies x.[c,c,c,c,c]=0. Thus x.(x+c)=x.x=1. y=x+c except for last element, and x.y must be 0. Thus changing the last element from x_last+c=x_last(n+1)/(n-1) to -x_last must change the dot product from 1 to 0. Thus x_lastx_last(n+1)/(n-1) = x_last(-x_last)+1, and x_last = sqrt((n-1)/(2n)). (In the example, 0.632 = sqrt(4/10)). So this limits the values of n for which such rational solutions can exist to those for which (n-1)/(2n) is a square. Up to a million such values are 1, 2, 9, 50, 289, 1682, 9801, 57122, 332929. It turns out that these are actually sufficient requirements to make a solution optimal. ANY x which fulfills sum(x)=0, x.x=1, x_last=sqrt(n-1)/(2n)) gives a solution by setting y=x+c except y_last. To find an optimal solution of say length 50, it's now enough to find a vector of length 50 which fulfills these conditions: sum(x)=0 x_last = sqrt(49/100) = 7/10 x.x = 1 (7/10)^2 = 49/100, so we need to fill the remaining elements of x with values that have these properties: they sum to -7/10, and their squares sum to 51/100. We'll just take -7/10, which leaves sum 0 and square-sum 2/100, and then add -1/10 and 1/10 which doesn't alter sum and fills square sum. (The published solution from Anders Kaseorg is one special case of constructing some values that have the required sum and sum of squares, but there are lots of other possibilities.) So now we have x=[-7/10, -1/10, 1/10, 0, 0, ..., 7/10] and y=x+c, where c=x_last * 2/(n-1)=7/245, except last element. y = [-7/10+7/245, -1/10+7/245, 1/10+7/245, 7/245, 7/245, ..., -7/10] You can verify that these give a rational solution of length 50, which is valid (x.x=y.y=1, sum(x)=sum(y)=0, x.y=0), and fulfills the optimality condition f(x,y)=4.