Integral complete 4-partite graphs

Question

For given block sizes $a<b<c<d$, consider the complete 4-partite graph $K_{a,b,c,d }$.

• Can such a graph be integral, i.e. have only integer eigenvalues?

It is easy to see that the four nonzero eigenvalues of $K_{a,b,c,d }$ are the same as those of $$\begin{pmatrix} 0&b&c&d\\ a&0&c&d\\ a&b&0&d\\ a&b&c&0 \end{pmatrix}$$ because the corresponding eigenvectors must have the same entry inside each block.
So we can consider instead the characteristic polynomial of this matrix, $$\lambda^4-(ab+ac+ad+bc+bd+cd) \lambda^2- 2( a b c+abd+acd+bcd) \lambda-3 a b c d.$$

Though not related, it reminds me of the question about the existence of perfect Euler bricks.
The corresponding question for tripartite graphs with pairwise different block sizes has been settled here.

I have done an exhaustive computer search for all quadruples with $d\leqslant 200$ and found none with four integer eigenvalues. Many of them have exactly one integer eigenvalue, and a few have two, e.g. $K_{8,15,32,40}$. The complete list of the latter solutions (that is, the coprime ones) follows, including each time the two integer eigenvalues $λ1 <λ2$.

        d     c     b    a       λ1    λ2   

       40    32    15    8      -36   -20
       42    28    15    7      -35    63
       56    41    32   24      -36   112
       64    44    24    9      -54   -96
       72    18     9    2      -12    54 
       77    48    35    3      -63   -40
       79    75    35   11      -77   -45   
       91    89    40   15      -90   -52                   
       93    75    40    7      -84   -50 
      102    70    63   50      -54   210                              
      104    56    48   39      -84   -52
      105    96    70   55      -80   -60
      112    56    40    7      -84   140 
      112    57    30   21      -84   -24   
      112   100    99   84     -108   -88  
      117    83    40   25     -100   -54 
      117    90    40   18      -54   180  
      117    91    48   13     -104   182 
      119    54    24   14      -84   -34
      128    80    63   12      -70   192 
      130    39    18   13      -78   -26
      130    91    67   32     -112   -39
      133    47    40   15      -90   -19
      135   110    72   54      -60   270
      144    54    14    9      -24   126
      145    70    33   15     -105   -45 
      160    40     8    7      -84   -16   
      160   104    65   40      -80   260   
      165    22    21    7      -77    -9   
      165   102    44   12     -132   -60   
      168    40    15   12      -90   -24   
      168    40    32   25     -100   -36   
      168    57    25   15     -105   -36   
      175    80    69   63     -135   -75
      175    85    63   60     -135   -75
      175    87    63   55     -135   -75
      175    90    63   45     -135   -75
      175    93    63   30     -135   -75
      175    95    63   15     -135   -75
      175    96    63    5     -135   -75
      175   111    55   39     -143   -75
      175   141   130   63     -135   -75
      175   150   125   63     -135   -75
      175   155   123   63     -135   -75
      175   165   120   63     -135   -75
      176    40    15    4      -90   -22   
      180   175   117   63     -135   -75
      187   163    75   35     -175   -99
      192    88    33   12      -48   198
      195    57    48   35     -126   -39
      195   117   104   69      -78   351
      195   144   116  104     -174  -130
      195   175   115   63     -135   -75
      200    52    48   35     -126   -50
      200    98    35    2      -50   196

• Note that in those quadruples, a few primes do occur. But among the eigenvalues... the first prime ($-19$) only appears at $d=133$ and is so far the only one!
• So far, all prime factors of the eigenvalues divide at least one of $a,b,c,d$.

• Moreover, if the two eigenvalues have a common prime factor, it divides most often (but sadly not always) three of $a,b,c,d$.

• And now: What is happening for $d=175$? All solutions except $(175, 111,55, 39)$ not only have the same two integer eigenvalues $-135$ and $-75$, but also have $63$ among the block sizes. This includes as well the solutions $(180, 175, 117, 63 )$ and $(195, 175, 115, 63)$ and possibly more with larger $d$'s. How to explain such a "cluster"?
  Similarly, the pair of block sizes $(40,7)$ co-occurs several times with the eigenvalue $-84$.

This all is obviously intriguing and raises the following question, which is interesting on its own, whether or not integral graphs exist:

• In terms of elliptic functions, is it possible to characterize the solutions $(a,b,c,d)$ with two integer nonzero eigenvalues?

Answer 1

• Can such a graph be integral, i.e. have only integer eigenvalues?

Yes. Two examples are $(a,b,c,d) = (441, 744, 1225, 5635)$, with eigenvalues $-945$, $-525$, $-3038$, $4058$, and $(a,b,c,d) = (1575, 1900, 4500, 33516)$, with eigenvalues $-1710$, $-2940$, $-14250$, $18900$. There are infinitely many others, even if we require that they be "primitive" (no common factors other than $\pm 1$) so one cannot claim new examples just be scaling $(a,b,c,d)$ to $(ka,kb,kc,kd)$.

• In terms of elliptic functions, is it possible to characterize the solutions (a,b,c,d) with two integer nonzero eigenvalues?

For general $(x,y,a)$, the triples $(b,c,d) \in {\bf Q}^3$ such that $x,y$ are eigenvalues of $K_{a,b,c,d}$ are parametrized by an elliptic curve. Most rational points on this curve don't yield integer solutions, but rational solutions with $b,c,d>0$ are enough because we can clear denominators to make them integral, and then permute to get $a<b<c<d$ as long as they're pairwise distinct.

---

Let $P(a,b,c,d;\lambda)$ be the characteristic polynomial $$ \lambda^4 - (ab+ac+ad+bc+bd+cd) \lambda^2 - 2 (abc+abd+acd+bcd) \lambda - 3 a b c d. $$ of $K_{a,b,c,d}$, as exhibited in the problem statement. Given two eigenvalues $x,y$, we can eliminate one of the block sizes, say $d$, from the simultaneous linear equations $$P(a,b,c,d;x) = P(a,b,c,d;y) = 0.$$ This gives a surface $Q(a,b,c) = 0$ that is of degree $2$ in each of the variables $a,b,c$; choosing one of them, say $a$, yields a curve of degree $2$ in each of the others, which is typically an elliptic curve. That curve always has a few automatic points such as those with $b=0$ and $c=0$; starting from those and using the group law on an elliptic curve we can produce infinitely many others.

This curve has a somewhat special form $C^2 = D_1(a,b) D_2(a,b) D_3(a,b)$ where $D_1,D_2,D_3$ have bidegrees $(1,1)$, $(1,1)$, $(2,2)$ in $a$ and $b$. This form is obtained by factoring the discriminant of $Q(a,b,c)$ as a quadratic in $c$; explicitly $$ D_1 = x^3 + (x^2 + 2(a+b)x + 3ab)y - abx, \quad D_2 = y^3 + (y^2 + 2(a+b)y + 3ab)x - aby, $$ $$ D_3 = x^2 y^2 + 2(a+b)(x+y)xy + ab(3x^2 + 4xy + 3y^2) - 3(ab)^2. $$ For most $(x,y,a)$, the quartic $D_1,D_2,D_3$ in $b$ has distinct roots; but for some special choices there are repeated roots, and then the curve $C^2 = D_1 D_2 D_3$ can be rational. It turns out that if $3(x+3y)(3x+y)$ is a square then we can choose $a$ so that $D_1 D_2 D_3$ is a perfect square; explicitly we find that this happens for $$ (x:y:a) = (3 (r-s) (r+3s) (r^2-s^2) : (r-s) (r+3s) (9s^2-r^2) : (r+s) (r-3s) (r^2+3s^2)) $$ for some $r,s$. This gives a one-parameter family of $(b,c,d)$ such that $P(a,b,c,d;\lambda)$ factors as $(\lambda-x) (\lambda-y)$ times some quadratic in $\lambda$, and we can then require that quadratic to have square discriminant, which yields a new elliptic curve that has a few automatic rational points such as those with $c=0$; again we cannot use those solutions directly but can combine them using the group law. This yields complicated parametric families; instead of carrying out such a computation, I just searched for simple rational points on the curves arising from $(r:s) = (2:-1)$ and $(4:1)$, and found in each case the point giving rise to one of the solutions at the top of this answer.