Ponder This Challenge - April 2022 - Minimizing a sum for two orthogonal vectors

Minimizing a sum for two orthogonal vectors

This month’s puzzle is based on a suggestion by Marco Bellocchi. Thanks, Marco!
Let $x,y\in\mathbb{R}^n$ be two vectors, and define the function $f(x,y) = \sum_{i=1}^n\sum_{j=1}^n(|x_i-x_j|-|y_i-y_j|)^2$ We wish to minimize $f$, subject to the following constraints on $x,y$: The vectors need to be orthogonal to each other and to the vector $(1,1,\ldots,1)$ and of norm 1, i.e.,

1. $\sum_{i=1}^nx_i^2=\sum_{i=1}^ny_i^2=1$
2. $\sum_{i=1}^nx_i=\sum_{i=1}^ny_i=0$
3. $\sum_{i=1}^nx_iy_i=0$ The lower bound for $f$ appears to be 4, but we know of no proof for general $n$. Nevertheless, we refer to a pair $x,y$ giving $f(x,y)=4$ as being an "optimal solution". For example, suppose $n=5$ and x = [-0.3562014 , 0.63245526, -0.3688259 , -0.36163773, 0.45420977] y = [-0.03997346, -0.6324558 , -0.05259805, -0.04540969, 0.77043701] Then $x,y$ are very close to being an optimal solution, up to a small error of at most 0.0000001 Your goal For $n=20$, find a pair of $x,y$ that are 0.0000001-close to being an optimal solution. Give your solution in the exact format given above. A bonus "*" will be given for finding an **exact** solution ($f(x,y)=4$) where $x,y$ are both rational vectors ($x,y\in\mathbb{Q}^n$), for some $n$ at least 5. Give your solution in a format similar to that above, but with numbers written as "a/b", e.g., x = [1/2, 1/3, 1/6] A bonus "**" will be given for finding an exact rational solution for any $n\ge 40$, or for proving 4 is indeed the minimum value of $f$. (We do not know of such a solution or such a proof.)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  April 2022 Solution:A non-exact solution can be found using optimization algorithms, but it is possible to find a closed-form formula for the optimal solutions. An excellent description, given below, was sent to us by Anders Kaseorg -thanks Anders!

  For all i + j + 1 = n, one optimal solution is

  x = [
  √(nj/i) − 1 repeated i times,
  −√(ni/j) − 1 repeated j times,
  n − 1
  ] / √(2n(n − 1)),
  y = [
  √(nj/i) + 1 repeated i times,
  −√(ni/j) + 1 repeated j times,
  −n + 1
  ] / √(2n(n − 1)).

  For example, at i = 4, j = 15, n = 20, we get

  x = [
  0.277866618713, 0.277866618713, 0.277866618713, 0.277866618713,
  -0.120044594164, -0.120044594164, -0.120044594164,
  -0.120044594164, -0.120044594164, -0.120044594164,
  -0.120044594164, -0.120044594164, -0.120044594164,
  -0.120044594164, -0.120044594164, -0.120044594164,
  -0.120044594164, -0.120044594164, -0.120044594164,
  0.689202437605
  ]
  y = [
  0.350414243724, 0.350414243724, 0.350414243724, 0.350414243724,
  -0.047496969153, -0.047496969153, -0.047496969153,
  -0.047496969153, -0.047496969153, -0.047496969153,
  -0.047496969153, -0.047496969153, -0.047496969153,
  -0.047496969153, -0.047496969153, -0.047496969153,
  -0.047496969153, -0.047496969153, -0.047496969153,
  -0.689202437605
  ]

  Some of these solutions are rational. An infinite family of them can be constructed using the Pell numbers

  P[0] = 0,
  P[1] = 1,
  P[k] = 2P[k−1] + P[k−2],

  as follows: for all k ≥ 0, one rational optional solution is

  x = [
  (P[2k+1] + P[2k+2] − 1)/P[4k+4] repeated P[2k+2]² times,
  (−P[2k+1] − P[2k+2] − 1)/P[4k+4] repeated P[2k+2]² times,
  (P[2k+2]² − 1)/P[4k+4]
  ],
  y = [ (P[2k+1] + P[2k+2] + 1)/P[4k+4] repeated P[2k+2]² times,
  (−P[2k+1] − P[2k+2] + 1)/P[4k+4] repeated P[2k+2]² times,
  (−P[2k+2]² + 1)/P[4k+4]
  ].

  For example, at k = 1, we get this solution with n = 289:

  x = [
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51, 2/51,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68, -3/68,
  12/17
  ]
  y = [
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68, 3/68,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51, -2/51,
  -12/17
  ]

Solvers

• **Bert Dobbelaere (30/3/2022 9:34 PM IDT)
• **Anders Kaseorg (31/3/2022 1:29 AM IDT)
• Richard Gosiorovsky (31/3/2022 5:19 PM IDT)
• **Bertram Felgenhauer (1/4/2022 7:43 AM IDT)
• Kerry Soileau (1/4/2022 3:47 PM IDT)
• Graham Hemsley (1/4/2022 5:47 PM IDT)
• Joerg Schepers (1/4/2022 8:43 PM IDT)
• **Phil Proudman (2/4/2022 9:03 PM IDT)
• **Laurent Lessard (3/4/2022 7:58 AM IDT)
• Daniel Chong Jyh Tar (3/4/2022 1:44 PM IDT)
• Balakrishnan V (4/4/2022 2:27 AM IDT)
• **Uoti Urpala (4/4/2022 2:55 AM IDT)
• Gary M. Gerken (4/4/2022 3:28 AM IDT)
• Sachal Mahajan (4/4/2022 6:20 AM IDT)
• Lorenz Reichel (5/4/2022 2:56 PM IDT)
• **Alper Halbutogullari &Ali Ekber Gurel (6/4/2022 9:38 AM IDT)
• *Evert van Dijken (6/4/2022 12:04 PM IDT)
• Paul Revenant (7/4/2022 5:10 PM IDT)
• Stephen Barr (12/4/2022 7:15 AM IDT)
• Fabio Michele Negroni (13/4/2022 1:15 PM IDT)
• **David Greer (14/4/2022 2:32 PM IDT)
• **Vladimir Volevich (14/4/2022 8:10 PM IDT)
• **Nyles Heise (15/4/2022 8:58 AM IDT)
• Clive Tong (16/4/2022 11:14 AM IDT)
• Harald Bögeholz (17/4/2022 5:25 AM IDT)
• Tamir Ganor & Shouky Dan (17/4/2022 5:15 PM IDT)
• John Goh (18/4/2022 5:13 AM IDT)
• **Oleg Vlasii (19/4/2022 6:32 PM IDT)
• Dan Dima (21/4/2022 8:12 PM IDT)
• *Reda Kebbaj (23/4/2022 2:07 AM IDT)
• Sri Mallikarjun J (23/4/2022 10:08 AM IDT)
• **Latchezar Christov (23/4/2022 2:05 PM IDT)
• **Aaron Kim (23/4/2022 4:55 PM IDT)
• **Elliot Hong (23/4/2022 5:54 PM IDT)
• **Grace Park (24/4/2022 4:53 PM IDT)
• Teawoo Kim (24/4/2022 5:58 PM IDT)
• Nir Lavee & Omer Shechter (24/4/2022 6:23 PM IDT)
• **Joon Park (25/4/2022 5:38 AM IDT)
• **Keun Hyong Kwak (25/4/2022 7:23 AM IDT)
• Andreas Knüpfer (25/4/2022 6:32 PM IDT)
• Kang Jin Cho (25/4/2022 8:13 PM IDT)
• **Austin Lee (25/4/2022 9:17 PM IDT)
• Chris Shannon (26/4/2022 8:26 PM IDT)
• Sebastian Bohm & Martí Bosch (27/4/2022 11:43 PM IDT)
• Daniel Bitin (29/4/2022 12:57 PM IDT)
• **Motty Porat (30/4/2022 12:40 AM IDT)
• Rob Pratt (30/4/2022 1:03 AM IDT)
• Alexander Gramolin (30/4/2022 7:36 AM IDT)
• Albert Stadler (30/4/2022 10:42 AM IDT)
• Tim Walters (1/5/2022 1:08 AMIDT)
• **Radu-Alexandru Todor (1/5/2022 3:03 AM IDT)
• Amos Guler (2/5/2022 8:54 PM IDT)
• **Li Li (3/5/2022 7:10 AM IDT)