TAOCP 3.3.4 Exercise 17

For each dimension $t$, Algorithm S examines all integer vectors U=(u_1,\ldots,u_t) satisfying (15), and computes

taocpmathematicsalgorithmsvolume-2

Section 3.3.4: The Spectral Test

Exercise 17. [**] $[20]$ Modify Algorithm S so that, in addition to computing the quantities $\nu_t$, it outputs all integer vectors $(u_1, \ldots, u_t)$ satisfying (15) such that $u_1^2 + \cdots + u_t^2 = \nu_t^2$, for $2 \le t \le T$.

Verified: yes
Solve time: 2m38s

For each dimension $t$, Algorithm S examines all integer vectors

$$ U=(u_1,\ldots,u_t) $$

satisfying (15), and computes

$$ \nu_t^2=\max (u_1^2+\cdots+u_t^2). $$

To obtain all extremal vectors simultaneously with the computation of $\nu_t$, it suffices to augment the algorithm by storing every vector that attains the current maximum.

Let $L_t$ denote a list associated with dimension $t$. Initially set

$$ \nu_t^2 \gets -1,\qquad L_t\gets \emptyset . $$

Whenever Algorithm S generates a vector

$$ U=(u_1,\ldots,u_t) $$

satisfying (15), compute

$$ s(U)=u_1^2+\cdots+u_t^2 . $$

Then replace the step that updates $\nu_t$ by the following:

  1. If $s(U)>\nu_t^2$, set

$$ \nu_t^2\gets s(U), $$

and replace the list $L_t$ by the singleton list

$$ L_t\gets {U}. $$ 2. If $s(U)=\nu_t^2$, append $U$ to $L_t$. 3. If $s(U)<\nu_t^2$, do nothing.

After all admissible vectors have been processed, output $\nu_t$ together with the contents of $L_t$.

This modification is correct because Algorithm S already enumerates every integer vector satisfying (15). Hence every admissible vector $U$ is examined exactly once. During the enumeration, $\nu_t^2$ is always the largest value of $s(U)$ seen so far, and $L_t$ consists precisely of those vectors attaining that value.

Indeed, suppose that after processing some collection of admissible vectors,

$$ \nu_t^2=M. $$

By construction:

  • every vector in $L_t$ satisfies $s(U)=M$;
  • whenever a larger value is found, the old list is discarded and replaced by the new maximizer;
  • whenever another vector attains the same value $M$, it is appended to $L_t$.

Therefore, after the enumeration is complete,

$$ M=\max s(U)=\nu_t^2, $$

and $L_t$ contains exactly all vectors satisfying

$$ u_1^2+\cdots+u_t^2=\nu_t^2. $$

Thus Algorithm S is modified to output all extremal vectors without any additional exhaustive search.

$\square$