11
$\begingroup$

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}$.

$\endgroup$
4
  • $\begingroup$ Presumably that first condition "$d_i/n$" is $d_i | n$. $\endgroup$ Sep 16, 2013 at 15:56
  • $\begingroup$ @AllenKnutson, yes it is : $d_{i}$ divides $n$. $\endgroup$ Sep 16, 2013 at 16:00
  • $\begingroup$ 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$. $\endgroup$ Sep 16, 2013 at 16:08
  • $\begingroup$ @PeterMueller : You're right, it's a consequence of the previous conditions, thank you ! $\endgroup$ Sep 16, 2013 at 16:18

3 Answers 3

20
$\begingroup$

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: \begin{equation} 1+F_{2i-1}^2+F_{2i+1}^2=3F_{2i-1}F_{2i+1}. \end{equation} 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 \begin{equation} ca = (mb-a)a = b^2+1 \le b(b+1) \le ba \end{equation} 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.

$\endgroup$
4
  • 5
    $\begingroup$ 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$. $\endgroup$ Sep 16, 2013 at 17:58
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 18, 2013 at 12:03
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 18, 2013 at 15:10
  • $\begingroup$ Perhaps there is a link with the abc conjecture. $\endgroup$ Sep 20, 2013 at 20:34
3
$\begingroup$

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):
enter image description here

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$ :

enter image description here

Conjecture on upper-bounds (open) :

  • $M(r) \le 3.6r+21.6 $
  • $N(r) \le ln(r)^{2+ln(ln(ln(r)))/2}+2 $
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2013 at 15:29
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2013 at 17:50
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 19, 2013 at 18:33
  • $\begingroup$ @PeterMueller: See this post of Will Jagy. $\endgroup$ Sep 19, 2013 at 19:52
  • 1
    $\begingroup$ @SébastienPalcoux I have placed a copy of the English translation of Baulina's paper here: dl.dropboxusercontent.com/u/8101832/baulina.pdf $\endgroup$
    – j.c.
    Sep 20, 2013 at 10:17
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Do you know if there exists attempts for generalizing this result to the finite quantum groups ? $\endgroup$ Dec 31, 2013 at 9:49
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 31, 2013 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.