9
$\begingroup$

Problem:
IBM Research - Ponder This - January 2019 monthly contest (which was closed few days ago) leads to the problem:

Find sets $A = \{a_1,a_2,\ldots,a_n\}$, $B = \{b_1,b_2,\ldots, b_m\}$ such that $a_i+b_j = s_{ij}^2$
for $n\ge 4, m\ge 4$ (where $a_i,b_j,s_{ij}\in\mathbb{Z}$, $0\le a_1 < a_2 < \ldots < a_n$, $0\le b_1 < b_2 < \ldots < b_m$).

And it was said that nothing is known about solution for the case $n=m=5$.

Related links:


Approach:
If focus on the case $n=m$, then w.l.o.g. $a_1 \le b_1$; and since any solution $(A,B) =(\{a_i\}, \{b_j\})$ can be written in "shifted" form $(A',B')=(\{a_i-c\}, \{b_j+c\})$, $-$ we'll focus on solutions with $a_1 = 0$.

Actually, it's enough to write $a_i$, $b_j$ in the form:
$a_i = x_i^2 - \omega^2$,
$b_j = y_j^2$,
$( x_1 = \omega$, $ y_1 = \omega$, $ \omega\ge 0)$, to find solution of the problem.

To keep symmetry, one can write key numbers of solution in "square" table \begin{array}{c|c|c|c|c|c|} \color{tan}{-\omega^2} & \color{blue}{\omega^2} & \color{blue}{y_2^2} & \color{blue}{y_3^2} & \color{blue}{\ldots} & \color{blue}{y_m^2} \\ \hline \color{red}{\omega^2} & \color{gray}{\omega^2} & \color{gray}{y_2^2} & \color{gray}{y_3^2} & \ldots & \color{gray}{y_m^2} \\ \hline \color{red}{x_2^2} & \color{gray}{x_2^2} & s_{22}^2 & s_{23}^2 & \ldots & s_{2m}^2 \\ \hline \color{red}{x_3^2} & \color{gray}{x_3^2} & s_{32}^2 & s_{33}^2 & \ldots & s_{3m}^2 \\ \hline \color{red}{\vdots} & \color{gray}{\vdots} & \vdots & \vdots & \ddots & \vdots \\ \hline \color{red}{x_n^2} & \color{gray}{x_n^2} & s_{n2}^2 & s_{n3}^2 & \ldots & s_{nm}^2 \\ \hline \end{array} where $$s_{ij}^2 = \color{red}{x_i^2} + \color{blue}{y_j^2} - \omega^2.\tag{1}$$


Example:
One of $4\times 4$ examples:
$A = \{0, \; 282^2-18^2, \; 477^2-18^2,\; 1122^2 - 18^2\},$
$B=\{18^2, 234^2, 346^2, 514^2\}$ with appropriate table:

\begin{array}{c|c|c|c|c|} \color{tan}{-18^2} & \color{blue}{18^2} & \color{blue}{234^2} & \color{blue}{346^3} & \color{blue}{514^2} \\ \hline \color{red}{18^2} & \color{gray}{18^2} & \color{gray}{234^2} & \color{gray}{346^2} & \color{gray}{514^2} \\ \hline \color{red}{282^2} & \color{gray}{282^2} & 366^2 & 446^2 & 586^2 \\ \hline \color{red}{477^2} & \color{gray}{477^2} & 531^2 & 589^2 & 701^2 \\ \hline \color{red}{1122^2} & \color{gray}{1122^2} & 1146^2 & 1174^2 & 1234^2 \\ \hline \end{array}


Efforts:
I was/am excited to find $A,B$ for $n=m=5$. Unfortunately, without (essential) success: best result I can reach is finding two $5\times5$ tables-"siblings", which have $24$ of $25$ square numbers inside:

\begin{array}{c|c|c|c|c|c|} \color{tan}{-360^2} & \color{blue}{360^2} & \color{blue}{19240^2} & \color{blue}{41535^3} & \color{blue}{79560^2} & \color{blue}{161928^2} \\ \hline \color{red}{360^2} & \color{gray}{360^2} & \color{gray}{19240^2} & \color{gray}{41535^2} & \color{gray}{79560^2} & \color{gray}{161928^2} \\ \hline \color{red}{24696^2} & \color{gray}{24696^2} & 31304^2 & 48321^2 & 83304^2 & 163800^2 \\ \hline \color{red}{39060^2} & \color{gray}{39060^2} & 43540^2 & 57015^2 & \color{orange}{7855347600} & 166572^2 \\ \hline \color{red}{81480^2} & \color{gray}{81480^2} & 83720^2 & 91455^2 & 113880^2 & 181272^2 \\ \hline \color{red}{131460^2} & \color{gray}{131460^2} & 132860^2 & 137865^2 & 153660^2 & 208572^2 \\ \hline \end{array}

and

\begin{array}{c|c|c|c|c|c|} \color{tan}{-360^2} & \color{blue}{360^2} & \color{blue}{19240^2} & \color{blue}{41535^3} & \color{blue}{51480^2} & \color{blue}{161928^2} \\ \hline \color{red}{360^2} & \color{gray}{360^2} & \color{gray}{19240^2} & \color{gray}{41535^2} & \color{gray}{51480^2} & \color{gray}{161928^2} \\ \hline \color{red}{24696^2} & \color{gray}{24696^2} & 31304^2 & 48321^2 & 57096^2 & 163800^2 \\ \hline \color{red}{39060^2} & \color{gray}{39060^2} & 43540^2 & 57015^2 & 64620^2 & 166572^2 \\ \hline \color{red}{81480^2} & \color{gray}{81480^2} & 83720^2 & 91455^2 & \color{orange}{9289051200} & 181272^2 \\ \hline \color{red}{131460^2} & \color{gray}{131460^2} & 132860^2 & 137865^2 & 141180^2 & 208572^2 \\ \hline \end{array}


Question: Is it possible to find solution for the case $5\times 5$? Does there exist one? Any ideas or estimations?

$\endgroup$
  • 1
    $\begingroup$ I don't really understand your tables. For example in the last table, $360^2+360^2$ is not $360^2$ so the condition $a_1+b_1=s_{11}^2$ seems to be violated. One remark on the problem: what your are doing is writing down pythagorean triples which was also my first idea. There are long lists of such triples, probably some trial and error using such lists helps you finding an example? Also note that you can set $a_i=b_i$ so you only have to find one "triangle" in such a table. $\endgroup$ – James Feb 8 at 10:24
  • $\begingroup$ @James: central cells of the table are calculated by formula $(1)$: for example, from last table: $$\color{red}{39060^2} + \color{blue}{19240^2} \underline{-\color{tan}{360^2}} = 43540^2;$$ $$\color{red}{131460^2}+\color{blue}{161928^2} \underline{-\color{tan}{360^2}}=208572^2;$$ $\endgroup$ – Oleg567 Feb 8 at 10:38
  • $\begingroup$ @James: In the case when $\omega=0$, if omit (trivial) $1$st column and row of central part of table, $-$ we'll get table with pythagorean triples: \begin{array}{c|c|c|c|} + & \color{blue}{952^2} & \color{blue}{1800^2} & \color{blue}{3536^3} \\ \hline \color{red}{960^2} & 1352^2 & 2040^2 & 3664^2 \\ \hline \color{red}{1785^2} & 2023^2 & 2535^2 & 3961^2 \\ \hline \color{red}{6630^2} & 6698^2 & 6870^2 & 7514^2 \\ \hline \end{array} but I can't find better than $3\times 3$ ... $\endgroup$ – Oleg567 Feb 8 at 10:55
  • 2
    $\begingroup$ bib.irb.hr/datoteka/635146.dujella-elsholtz01k.pdf might be of interest... thery say 3*N is possible for every N, but it is stated that 4*N is NOT possible for every N (proven in other papers, it could be interesting to know the bound...). Maybe pushing their techniques one might get something on the case 5... $\endgroup$ – StheW Feb 15 at 0:58
  • $\begingroup$ @StheW thanks! Really interesting link and bibliography on the problem. $\endgroup$ – Oleg567 Feb 16 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.