# A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :

• $d_{i}\vert n$
• $1=d_{1}<d_{2} \le d_{3} \le ... \le d_{r}$
• $gcd(d_{2},d_{3},...,d_{r}) = 1$

We call $r$ the rank of the partition.

Examples :

• $60 = 1+3^{2}+3^{2}+4^{2}+5^{2}$
• $168 = 1+3^{2}+3^{2}+6^{2}+7^{2}+8^{2}$

Remark : Let $G$ be a non-cyclic finite simple group, and $(H_{i})_{i}$ its irreducible representations, then : $$ord(G) = \sum_{i} dim(H_{i})^{2}$$ is an example. The first example comes from the group $A_{5}$, and the second, from the group $A_{1}(7)$.
Of course, there are examples not coming from a group : $60 = 1 + 3^{2} + 5^{2}+5^{2}$

Problem : Are there only finitely many such partitions for a fixed rank $r$ ?

Motivation : The study of finite quantum groups (see here).

Final remark: Let $p_{r}(n)$ be the number of such partitions for $n$, of rank $r$.
If the problem has a positive answer, then $N_{r} = max\{n : p_{r}(n) \ne 0 \} < \infty$
In this case, the generating function $P_{r}(x) = \sum_{n}p_{r}(n)x^{n}$, is a polynomial of degree $N_{r}$.
Bonus problem : Find an evaluation of the number $N_{r}$.

• Presumably that first condition "$d_i/n$" is $d_i | n$. – Allen Knutson Sep 16 '13 at 15:56
• @AllenKnutson, yes it is : $d_{i}$ divides $n$. – Sebastien Palcoux Sep 16 '13 at 16:00
• What is the third condition good for? The $gcd$ divides $n$, and also $n-d_1^2=n-1$, so it is automatically equal to $1$. – Peter Mueller Sep 16 '13 at 16:08
• @PeterMueller : You're right, it's a consequence of the previous conditions, thank you ! – Sebastien Palcoux Sep 16 '13 at 16:18

Update: Sebastien and I just found out that the equation $X_1^2+\dots+X_r^2=mX_1\dots X_r$ which evolved in the comments below is a classical topic, named the Hurwitz equation. See this encyclopedia entry. It was actually discussed on MO before, see this post. So most of the comments below are obsolete.

Existence: For $r=3$ there are infinitely many such partitions. Let $F_i$ be the $i$th Fibonacci number. Then: $$1+F_{2i-1}^2+F_{2i+1}^2=3F_{2i-1}F_{2i+1}.$$ This follows from Cassini's identity $F_{n-1}F_{n+1}-F_n^2=(-1)^n$ upon replacing $F_n$ with $F_{n+1}-F_{n-1}$, and setting $n=2i$.

Uniqueness: We now show the following:

Let $1\le b\le a$ be integers such that $abm=a^2+b^2+1$ for an integer $m$. Then $m=3$ and either $a=b=1$, or $b=F_{2i-1}$, $a=F_{2i+1}$.

If $a=b$, then of course $a=b=1$ and $m=3$. Suppose now that $b<a$. Set $c=mb-a$. Then \begin{align} c^2+b^2+1 &= b^2m^2-2abm+a^2+b^2+1\\ &= b^2m^2-2abm +mab\\ &= mb(bm-a)\\ &= mbc \end{align} So the transformation $(a,b)\mapsto (b,mb-a)=(b,c)$ sends $(a,b)$ to another solution $(b,c)$. Note that $c>0$ as $b>0$. From $$ca = (mb-a)a = b^2+1 \le b(b+1) \le ba$$ we obtain $c\lt b$, unless $b=1$ and $a=2$. So by descend we finally arrive at $(a,b)=(2,1)$, hence $m=3$.

We see that $m=3$, and that every solution of $a^2+b^2+1=3ab$ with $a>b$ has the form $(a_k,a_{k-1})$, where $(a_k)$ is the sequence defined by $a_1=1$, $a_2=2$ and $a_k=3a_{k-1}-a_{k-2}$. However, the sequence $F_{2i+1}$ fulfills this recurence, and the assertion follows.

• Remark : If $n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$ is an admissible partition (rank $r$), then $n + n^{2} = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r} + n^{2}$ is also admissible (rank $r+1$). So your infinite sequence at rank $3$ generates infinite sequences for all rank $>3$. – Sebastien Palcoux Sep 16 '13 at 17:58
• I suspect the following: Fix the rank $r$ and $m$. Then there is a unique tuple $1=a_1\le a_2\le\dots\le a_r$ with $\sum a_i^2=m\prod a_i$ such that $ma_1a_2\dots a_{r-1}-a_r\ge a_r$. If true, we can descend to a unique start tuple. Furthermore, I suspect that $m\le r$. (For $r\ge 5$, other values for $m$ besides $r$ are possible.) Proving these things even for $r=4$ seems to get a little involved. – Peter Mueller Sep 18 '13 at 12:03
• In order to study this, one can (and should) give up the restriction $a_1=1$. So maybe a new question could be: Let $r\ge3$ and $m\ge1$. What are the integral points of the variety $X_1^2+X_2^2+\dots+X_r^2=mX_1X_2\dots X_r$? Here $r=3$ is covered by a slight enhancement of my answer. The case $r=4$ looks doable, but involved. – Peter Mueller Sep 18 '13 at 15:10
• Perhaps there is a link with the abc conjecture. – Sebastien Palcoux Sep 20 '13 at 20:34

Some experimental results for the Markoff-Hurwitz equation : $$X_{1}^{2} + X_{2}^{2} + ... + X_{r}^{2} = mX_{1}X_{2}...X_{r}$$ for $m \ge 1$, $X_{i} \in \mathbb{N}$ and $1 \le X_{1} \le X_{2} \le ... \le X_{r}$

Let $n = mX_{1}X_{2}...X_{r}$.

Remark : If $(a_{1},a_{2}, ... ,a_{r})$ is a solution, then $(a_{1},a_{2}, ... ,a_{r-1},b_{r} )$ also (up to sorting), with $b_{r} =ma_{1}a_{2}...a_{r-1} - a_{r}$. It follows that each solution comes from a fundamental, checking : $$mX_{1}X_{2}...X_{r-1} \ge 2 X_{r}$$ Here are the fundamental solution computed for $n<100000$ and $3 \le r \le 14$:

rank $r=3$ :
$m=1$ : $(3,3,3)$ : $n=27$
$m=3$ : $(1,1,1)$ : $n=3$

rank 4 :
$1$ : $(2,2,2,2)$ : $16$
$4$ : $(1,1,1,1)$ : $4$

rank 5 :
$1$ : $(1,1,3,3,4)$ : $36$
$4$ : $(1,1,1,1,2)$ : $8$
$5$ : $(1,1,1,1,1)$ : $5$

rank 6 :
$3$ : $(1,1,1,1,2,2)$ : $12$
$6$ : $(1,1,1,1,1,1)$ : $6$

rank 7 :
$1$ : $(1, 1, 1, 2, 2, 2, 3)$ : $24$
$2$ : $(1, 1, 1, 1, 2, 2, 2)$ : $16$
$3$ : $(1, 1, 1, 1, 1, 2, 3)$ : $18$
$5$ : $(1, 1, 1, 1, 1, 1, 2)$ : $10$
$7$ : $(1, 1, 1, 1, 1, 1, 1)$ : $7$

rank 8 :
$1$ : $(1, 1, 1, 1, 2, 2, 2, 4)$ : $32$
$8$ : $(1, 1, 1, 1, 1, 1, 1, 1)$ : $8$

rank 9 :
$6$ : $(1, 1, 1, 1, 1, 1, 1, 1, 2)$ : $12$
$9$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $9$

rank 10 :
$1$ : $(1, 1, 1, 1, 1, 1, 1, 3, 4, 4)$ : $48$
$2$ : $(1, 1, 1, 1, 1, 1, 1, 2, 2, 3)$ : $24$
$4$ : $(1, 1, 1, 1, 1, 1, 1, 1, 2, 2)$ : $16$
$6$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 3)$ : $18$
$10$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $10$

rank 11 :
$2$ : $(1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4)$ : $32$
$3$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3)$ : $27$
$7$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)$ : $14$
$11$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $11$

rank 12 :
$12$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $12$

rank 13 :
$1$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 5)$ : $60$
$3$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4)$ : $36$
$4$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3)$ : $24$
$7$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3)$ : $21$
$8$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)$ : $16$
$13$ :$(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $13$

rank 14 :
$1$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 6)$ : $72$
$1$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3)$ : $36$
$4$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4)$ : $32$
$5$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)$ : $20$
$14$ : $(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)$ : $14$

Remark : At rank $14$ and $m=1$ there are two fundamental solutions.

Observations on the fundamental solutions (most of them are already known and proved) :

• This is a classification for $3 \le r \le 14$.
• $X_{1} \ne 1$ implies $X_{1} = ... = X_{r} \in \{ 2,3 \}$ and $r \in \{ 3,4\}$.
• Finiteness at fixed $r$.
• $1 \le m \le r$
• $X_{r}< 2r/m$ (open ?)
• Will Jagy's conjecture : $X_{r} \le \sqrt{9(r+6)/5}$

Graphics: for $3 \le r \le 2500$ (5 days of computer calculations)

1. The maximum $M(r)$ for $n$ at a fixed $r$ (for the fundamental solutions):

A repeating pattern is observed.
The stratification comes probably from the minimum value of $m$ for $r$ fixed.

2. The number $N(r)$ of fundamental solutions at a fixed $r$ :

Conjecture on upper-bounds (open) :

• $M(r) \le 3.6r+21.6$
• $N(r) \le ln(r)^{2+ln(ln(ln(r)))/2}+2$
• If you drop the assumption on integrality of the $X_i$, just say that $X_i\ge1$ is real and satisfies the remaining restrictions. Doesn't that probably already bound $X_r$ from above in terms of $r$ and $m$? It seems to me that this could be the case. – Peter Mueller Sep 19 '13 at 15:29
• No, I just found out that it is not true. For instance take $r=3$, $m=1$, and then consider the family $(a,b,c)$ with $a>2$, $b=2a/\sqrt{a^2-4}$, $c=ab/2$. Then $a^2+b^2+c^2=abc$, and $c$ fulfills the condition $c<ab/2$. Now with $a\to 2+$, we get $b$ and $c$ arbitrarily large. – Peter Mueller Sep 19 '13 at 17:50
• Update: Just found out that this kind of equations has been classically studied, beginning with Hurwitz! A short survey is contained in link.springer.com/article/10.1007/BF01236632 – Peter Mueller Sep 19 '13 at 18:33
• @PeterMueller: See this post of Will Jagy. – Sebastien Palcoux Sep 19 '13 at 19:52
• @SébastienPalcoux I have placed a copy of the English translation of Baulina's paper here: dl.dropboxusercontent.com/u/8101832/baulina.pdf – j.c. Sep 20 '13 at 10:17

Since the question started with examples coming from degrees of irreducible characters of groups, it is perhaps worth noting that if we limit ourselves to group examples, there are only finitely many of a given rank. Since the "rank" is the number of irreducible characters of the group, and that is equal to the number of conjugacy classes, an old result of Landau applies. It asserts that there is some function $L(r)$ such that if a $~finite~$ group $G$ has exactly $r$ classes, then $|G| \le L(r)$. (Note that the finiteness hypothesis is essential.) Landau's theorem appears as Theorem 4.13 of my algebra text (Algebra: A Graduate Course).

• Thank you for your answer. Do you know if there exists attempts for generalizing this result to the finite quantum groups ? – Sebastien Palcoux Dec 31 '13 at 9:49
• @Palcoux Sadly, I know nothing about quantum groups. The proof of Landau's theorem, however is elementary. It uses only the fact that the class sizes sum to the group order and divide the group order. – Marty Isaacs Dec 31 '13 at 16:53