Comptes Rendus Mathématique

Jean B. Lasserre

On the Christoffel function and classification in data analysis

Simona Settepanella

So Yamagata

On the non-very generic intersections in discriminantal arrangements

Paul-Emile Paradan

Comptes Rendus
Mathématique
Paul-Emile Paradan
The Horn cone associated with symplectic eigenvalues
Volume 360 (2022), p. 1163-1168
https://doi.org/10.5802/crmath.383
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l’édition scientifique ouverte
www.centre-mersenne.org
e-ISSN : 1778-3569
Comptes Rendus
Mathématique
2022, Vol. 360, p. 1163-1168
https://doi.org/10.5802/crmath.383
Representation theory / Théorie des représentations
The Horn cone associated with symplectic
eigenvalues
Paul-Emile Paradan∗, a
a IMAG, Univ Montpellier, CNRS, France
E-mail: paul-emile.paradan@umontpellier.fr
Abstract. In this note, we show that the Horn cone associated with symplectic eigenvalues admits the same
inequalities as the classical Horn cone, except that the equality corresponding to Tr(C ) = Tr(A) + Tr(B) is
replaced by the inequality corresponding to Tr(C ) ≥ Tr(A)+Tr(B).
2020 Mathematics Subject Classification. 00X99.
Manuscript received 20 February 2022, revised 22 May 2022, accepted 24 May 2022.
1. Introduction
We consider R2n equipped with its canonical symplectic structure Ωn = ∑nk=1 d xk ∧ d xk+n .
Recall that a family (ek )1≤k ≤2n is a symplectic basis of R2n , if Ωn(ek ,e`) = 0 if |k − `| 6= n and
Ωn(ek ,ek+n) = 1, ∀ k.
Williamson’s theorem [18] says that any positive definite quadratic form q : R2n → R can
be written q(v) = ∑k=1λk (v2k + v2k+n) where the (v j ) are the coordinates of the vector v ∈ R2n
relatively to a symplectic basis. The positive numbers λk , that one chooses so that
λ(q) := (λ1 ≥ ·· · ≥λn) ,
will be referred to as the symplectic eigenvalues of the quadratic form q . They correspond to the
frequencies of the normal modes of oscillation for the linear Hamiltonian system generated by q .
The object of study of this note concerns the symplectic Horn cone, denoted Hornsp(n), that
is defined as the set of triplets (λ(q1),λ(q2),λ(q1+q2)) where q1, q2 are positive definite quadratic
forms on R2n .
Example 1. In dimension 2, the symplectic eigenvalue λ(q) of a positive definite quadratic form
q(x1, x2) = ax21 +bx22 + cx1x2 is equal to 12
p
4ab − c2. It is straightforward to show that Hornsp(1)
is equal to the set of triplets (x, y, z) of positive numbers satisfying x + y ≤ z.
∗Corresponding author.
ISSN (electronic) : 1778-3569 https://comptes-rendus.academie-sciences.fr/mathematique/
1164 Paul-Emile Paradan
Our main Theorem states that Hornsp(n) is a convex polyhedral set. Before detailing it, let us
recall some related results.
In [17], A. Weinstein showed that for non-increasing n-tuples of positive real numbers a and
b, the set ∆sp(a,b) := {λ(q1 +q2) |λ(q1) = a,λ(q2) = b} is closed, convex and locally polyhedral.
Recently, several authors have realized that some inequalities obtained long ago in the context
of eigenvalues of Hermitian matrices still apply to symplectic eigenvalues:
• T. Hiroshima proved in [7] an analogue of Ky Fan inequalities:
k∑
j=1
λ j
(
q1 +q2
)≥ k∑
j=1
λ j
(
q1
)+ k∑
j=1
λ j
(
q2
)
.
• In [8], T. Jain and H. Mishra obtained an analogue of Lidskii inequalities:
k∑
j=1
λi j
(
q1 +q2
)≥ k∑
j=1
λi j
(
q1
)+ k∑
j=1
λ j
(
q2
)
for any subset {i1 < i2 < ·· · < ik }.
• In [2], R. Bhatia and T. Jain obtained an analogue of the Weyl inequalities:
λi+ j−1
(
q1 +q2
)≥λi (q1)+λ j (q2) .
As the previous results suggest, we now explain the strong relationship between Hornsp(n)
with the classical Horn cone. If A is a Hermitian n ×n matrix, we denote by s(A) = (s1(A) ≥ ·· · ≥
sn(A)) its spectrum. The Horn cone Horn(n) is defined as the set of triplets (s(A),s(B),s(A +B))
where A,B are Hermitian n ×n matrices.
Denote the set of cardinality r -subsets I = {i1 < i2 < ·· · < ir } of [n] := {1, . . . , n} by P nr . To each
I ∈P nr we associate:
• a weakly decreasing sequence of non-negative integers λ(I ) = (λ1 ≥ ·· · ≥ λr ) where
λa = n − r +a − ia for a ∈ [r ].
• the irreducible representation Vλ(I ) of GLr (C) with highest weight λ(I ).
If x = (x1, . . . , xn) ∈Rn and I ⊂ [n], we define |x |I =∑i ∈ I xi and |x | =∑ni=1 xi . Let us denote by
Rn+ the set of weakly decreasing n-tuples of real numbers.
A. Klyachko [10] has shown that an element (x, y, z) ∈ (Rn+)3 belongs to the cone Horn(n) if and
only if it satisfies |x|+ |y | = |z| and
|x|I +|y |J ≤ |z|K ((?)I ,J ,K )
for any r < n, for any I , J ,K ∈P nr such that the Littlewood-Richardson coefficient
cKI J := dim
[
Vλ(I ) ⊗Vλ(J ) ⊗V ∗λ(K )
]GLr (C)
is non-zero. P. Belkale [1] showed that the inequalities (?)I ,J ,K associated to the condition cKI J = 1
are sufficient. Finally A. Knutson, T. Tao, and C. Woodward [11] have proved that this smaller list
is actually minimal. We refer the reader to survey articles [3, 5] for details.
The main result of this note is the following Theorem. Let us denote by Rn++ the set of non-
increasing n-tuples of positive real numbers.
Theorem 2. An element (x, y, z) ∈ (Rn++)3 belongs to Hornsp(n) if and only if it satisfies
(1) |x|+ |y | ≤ |z|,
(2) (?)I ,J ,K for all (I , J ,K ) of cardinality r < n such that cKI J = 1.
Corollary 3. Let a,b ∈ Rn++. An element z ∈ Rn++ belongs to ∆sp(a,b) if and only if it satisfies
|a|+ |b| ≤ |z| and |a|I +|b|J ≤ |z|K for all (I , J ,K ) of cardinality r < n such that cKI J = 1.
Paul-Emile Paradan 1165
2. The causal cone of the symplectic Lie algebra
The 2n ×2n matrix Jn = ( 0 −InIn 0 ) defines a complex structure on R2n that is compatible with the
symplectic structure Ωn . The symplectic group Sp(R2n) is defined by the relation t g Jn g = Jn .
A matrix X belongs to the Lie algebra sp(R2n) of Sp(R2n) if and only the matrix Jn X is symmetric.
Moreover, Jn X is positive if and only ifΩn(X v, v) ≥ 0, ∀ v ∈R2n .
We call an invariant convex cone C in sp(R2n) a causal cone if C is nontrivial, closed, and
satisfies C ∩−C = {0}. A classical result [13, 14, 16] asserts that there are exactly two causal cones
in sp(R2n) : one, denoted by C(n), containing −Jn and its opposite −C(n). The causal cone C(n) is
determined by the following equivalent conditions : for X ∈ sp(R2n), we have
X ∈ C(n) ⇐⇒ Jn X is positive ⇐⇒ Tr
(
X g Jn g
−1)≥ 0, ∀ g ∈ Sp (R2n) .
Now we explain how is parameterized the interior C(n)0 of C(n). From the definition above,
we see first that X ∈ C(n)0 if and only if Jn X is positive definite.
The Lie algebra of the maximal compact subgroup K = Sp(2n,R)∩O(2n) is
k :=
{(
A B
−B A
)
, t A =−A, t B = B
}
.
If µ := (µ1, · · · , µn), we write ∆(µ) = Diag(µ1, · · · , µn) and X (µ) = ( 0 ∆(µ)−∆(µ) 0 ). We work with the
Cartan subalgebra t := {X (µ),µ ∈ Rn} of k and the corresponding maximal torus T ⊂ K . The
set of roots R relatively to the action of T on sp(R2n)⊗C are composed by the compact ones
Rc := {εi − ε j } and the non compact ones Rn = {±(εi + ε j )}. We work with the subsets of positive
roots R+c := {εi −ε j , i < j } and R+n := {εi +ε j }. The Weyl chamber t+ ⊂ t is defined by the relations
〈α,µ〉 ≥ 0, ∀ α ∈R+c , namely µ1 ≥ ·· · ≥ µn . The subchamber Cn ⊂ t+ is defined by the conditions
〈β,µ〉 > 0, ∀β ∈R+n . Thus X (µ) ∈Cn if and only if µ ∈Rn++.
If M ∈ sp(R2n), we denote by OM := {g M g−1, g ∈ Sp(R2n)} the corresponding adjoint orbit.
Lemma 4.
(1) M ∈ C(n)0 if and only if there exists X ∈Cn such that M ∈OX .
(2) Let µ ∈ Rn++, and M ∈ OX (µ). The symplectic eigenvalues of the positive definite quadratic
form q(v) = t v Jn M v =Ωn(M v, v) are the numbers µ1 ≥ ·· · ≥µn > 0.
Proof. The first point is a classical fact [14, 16]. If M = g X (µ)g−1 with g ∈ Sp(R2n), we see that
Ωn(M v, v) =Ωn
(
X (µ)g−1v, g−1v
)= n∑
k=1
µk
(
v2k + v2k+n
)
where each v j is the j th coordinate of the vector g−1v . 
Remark 5. In [15], we call the interior C(n)0 of C(n) the holomorphic cone, since any coadjoint
orbit OX ⊂ C(n)0 admits a canonical structure of a Kähler manifold with a holomorphic action
of K . These orbits are closely related to the holomorphic discrete series representations of the
symplectic group Sp(R2n).
Thanks to the previous Lemma 4, we see that the symplectic Horn cone admits the alternative
definition:
Hornsp(n) =
{
(x, y, z) ∈ (Rn++)3 ∣∣∣OX (z) ⊂OX (x) +OX (y)} .
In the next section, we explain the result of [15] concerning the determination of Hornsp(n).
1166 Paul-Emile Paradan
3. Convexity results
The trace on gl(R2n) provides an identification between sp(R2n) and its dual sp(R2n)∗: to X ∈
sp(R2n) we associate ξX ∈ sp(R2n)∗ defined by 〈ξX ,Y 〉 =−Tr(X Y ). Through this identification the
causal cone C(n) becomes
C̃(n) :=
{
ξ ∈ sp(R2n)∗ ;〈ξ,Ad(g )z〉≥ 0, ∀ g ∈ Sp (R2n)}
where z = −12 Jn . The identification sp(R2n) ' sp(R2n)∗ induces several identifications k' k∗, t' t∗
and t+ ' t∗+. In the latter cases the identifications are done through an invariant scalar product
(−,−) on k∗.The subchamber C̃n ⊂ t∗+ is defined by the conditions: (α,ξ) ≥ 0, ∀ α ∈ R+c , and
(β,ξ) > 0, ∀β ∈R+n .
Through sp(R2n) ' sp(R2n)∗, the symplectic Horn cone becomes
Hornhol
(
Sp
(
R2n
))
:=
{
(ξ1,ξ2,ξ3) ∈
(
C̃n
)3 ∣∣∣Oξ3 ⊂Oξ1 +Oξ2} .
Here we have kept the notations of [15].
We have a Cartan decomposition sp(R2n) = k⊕p with
p :=
{(
A B
B −A
)
, t A = A, t B = B
}
.
We denote by p+ the vector space p equipped with the complex structure ad(z) and the compati-
ble symplectic structureΩp+ (Y ,Y
′) :=−Tr(Jn[Y ,Y ′]): hereΩp+ (Y , [z,Y ]) > 0 for any Y 6= 0.
The action of the maximal compact subgroup K ⊂ Sp(R2n) on (p+,Ωp+ ) is Hamiltonian with
moment map
Φp+ : p
+ → k∗
defined by 〈Φp+ (Y ), X 〉 = 12Ωp+ ([X ,Y ],Y ). If Y = ( A BB −A ), we see that 〈Φp+ (Y ), Jn〉 = Tr(A2 +B 2)
= 12‖Y ‖2. Hence the moment mapΦp+ is a proper map.
We consider the following action of the group K 3 on the manifold K ×K :
(k1,k2,k3) · (g ,h) =
(
k1g k
−1
3 ,k2hk
−1
3
)
.
The action of K 3 on the cotangent bundle N := T ∗(K ×K ) is Hamiltonian with moment map
ΦN : N → k∗× k∗× k∗ defined by the relations1
ΦN
(
g1,η1; g2,η2
)= (−g1η1,−g2η2,η1 +η2) .
Finally we consider the Hamiltonian K 3-manifold N × p+, where p+ is equipped with the
symplectic structure Ωp+ . The action is defined by the relations: (k1,k2,k3) · (g ,h, X ) =
(k1g k−13 ,k2hk
−1
3 ,k3X ). Let us denote by Φ : N × p+ → k∗ × k∗ × k∗ the moment map relative
to the K 3-action:
Φ
(
g1,η1; g2,η2,Y
)= (−g1η1,−g2η2,η1 +η2 +Φp+ (Y )) . (1)
SinceΦ is proper map, the Convexity Theorem [9, 12] tell us that
∆
(
N ×p+) := Image(Φ)⋂ t∗+× t∗+× t∗+
is a closed, convex, and locally polyhedral set.
The map µ 7→ X (µ) defines an isomorphism of Rn with t' t∗ that induces an identification of
Rn++ with Cn ' C̃n . Recall that on t∗ 'Rn , we have a natural involution that sends µ= (µ1, . . . , µn)
to µ∗ := (−µn , . . . , −µ1). The following result is proved in [15, Theorem B].
Theorem 6. An element (x, y, z) ∈ (Rn++)3 belongs to Hornhol(Sp(R2n)) if and only if(
x, y, z∗
) ∈∆(N ×p+) .
1We use the identification T∗K ' K × k∗ given by left translations.
Paul-Emile Paradan 1167
Recall that a Hermitian matrix M majorizes another Hermitian matrix M if M −M ′ is positive
semidefinite (its eigenvalues are all nonnegative). In this case, we write M ≥ M ′.
Proposition 7. Let (x, y, z) ∈ (Rn+)3. Then (x, y, z∗) ∈∆(N ×p+) if and only if there exist Hermitian
matrices A,B ,C such that s(A) = x, s(B) = y, s(C ) = z and C ≥ A+B.
Proof. The map ( A −BB A ) 7→ A−i B defines an isomorphism between K and the unitary group U (n).
Let us denote by S2(Cn) the vector space of complex n ×n symmetric matrices that is equipped
with the following action of U (n): k · M = kM tk. The map ( A BB −A ) 7→ A − i B defines an isomor-
phism between the K -module p+ and the U (n)-module S2(Cn). Through this identifications the
moment mapΦp+ : p
+ → k∗ becomes the mapΦS2 : S2(Cn) → u(n) defined by the relations
ΦS2 (M) =−2i M M .
So we know that the moment polytope ∆ relative to the Hamiltonian action of U (n)3 on
T ∗U (n)×T ∗U (n)× S2(Cn) is equal to ∆(N × p+). A small computation shows that (x, y, z∗) ∈ ∆
if and only if there exist Hermitian matrices A,B ,C and M ∈ S2(Cn) such that
s(A) = x, s(B) = y, s(C ) = z and A+B +2M M =C .
The existence of M ∈ S2(Cn) satisfying the condition A+B +2M M =C is equivalent to C ≥ A+B .
The proof is then completed. 
S. Friedland [4] considered the following question: which eigenvalues (s(A),s(B),s(C )) can
occur if C ≥ A +B . His solution was in terms of linear inequalities, which includes Klyachko’s
inequalities, a trace inequality and some additional inequalities. Later, W. Fulton [6] proved the
additional inequalities are unnecessary. Let us summarizes their result in the following theorem.
Theorem 8 ( [4, 6]). A triple x, y, z ∈Rn+ occurs as the eigenvalues of n by n Hermitian matrices A,
B, C with C ≥ A +B if and only it satisfies |x| + |y | ≤ |z| and (?)I ,J ,K for all (I , J ,K ) of cardinality
r < n such that cKI J = 1.
The combination of Theorems 6 and 8 with Proposition 7 completes the proof of Theorem 2.
References
[1] P. Belkale, “Local systems on P−S for S a finite set”, Compos. Math. 129 (2001), no. 1, p. 67-86.
[2] R. Bhatia, T. Jain, “Variational principles for symplectic eigenvalues”, Can. Math. Bull. 64 (2021), no. 3, p. 553-559.
[3] M. Brion, “Restrictions de representations et projections d’orbites coadjointes (d’après Belkale, Kumar et Ressayre)”,
2011, Séminaire Bourbaki, http://www.bourbaki.ens.fr/TEXTES/1043.pdf.
[4] S. Friedland, “Finite and infinite dimensional generalizations of Klyachko’s theorem”, Linear Algebra Appl. 319
(2000), no. 1-3, p. 3-22.
[5] W. Fulton, “Eigenvalues, invariant factors, highest weights, and Schubert calculus”, Bull. Am. Math. Soc. 37 (2000),
no. 3, p. 209-249.
[6] ——— , “Eigenvalues of majorized Hermitian matrices and Littlewood-Richardson coefficients”, Linear Algebra Appl.
319 (2000), no. 1-3, p. 23-36.
[7] T. Hiroshima, “Additivity and multiplicativity properties of some Gaussian channels for Gaussian inputs”, Phys. Rev.
A 73 (2006), no. 1, article no. 012330 (9 pages).
[8] T. Jain, H. K. Mishra, “Derivatives of symplectic eigenvalues and a Lidskii type theorem”, Can. J. Math. 74 (2020),
no. 2, p. 457-485.
[9] F. Kirwan, “Convexity properties of the moment mapping III”, Invent. Math. 77 (1984), p. 547-552.
[10] A. A. Klyachko, “Stable bundles, representation theory and Hermitian operators”, Sel. Math., New Ser. 4 (1998), no. 3,
p. 419-445.
[11] A. Knutson, T. Tao, C. Woodward, “The honeycomb model of GLn (C) tensor products II: Puzzles determine facets of
the Littlewood-Richardson cone”, J. Am. Math. Soc. 17 (2004), no. 1, p. 19-48.
[12] E. Lerman, E. Meinrenken, S. Tolman, C. Woodward, “Non-Abelian convexity by symplectic cuts”, Topology 37 (1998),
no. 2, p. 245-259.
1168 Paul-Emile Paradan
[13] S. M. Paneitz, “Invariant convex cones and causality in semisimple Lie algebras and groups”, J. Funct. Anal 43 (1981),
p. 313-359.
[14] ——— , “Determination of invariant convex cones in simple Lie algebras”, Ark. Mat. 21 (1983), p. 217-228.
[15] P.-E. Paradan, “Horn problem for quasi-hermitian Lie groups”, J. Inst. Math. Jussieu (2022), p. 1-27.
[16] È. B. Vinberg, “Invariant convex cones and orderings in Lie groups”, Funct. Anal. Appl. 14 (1980), p. 1-10.
[17] A. Weinstein, “Poisson geometry of discrete series orbits and momentum convexity for noncompact group actions”,
Lett. Math. Phys. 56 (2001), no. 1, p. 17-30.
[18] J. Williamson, “On the algebraic problem concerning the normal forms of linear dynamical systems”, Am. J. Math.
58 (1936), p. 141-163.


The Horn cone associated with symplectic eigenvalues

Maciej Dołȩga

Jonathan Novak

Comptes Rendus
Mathématique
Maciej Dołȩga and Jonathan Novak
Procesi’s Conjecture on the Formanek-Weingarten Function is False
Volume 360 (2022), p. 1169-1172
https://doi.org/10.5802/crmath.391
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l’édition scientifique ouverte
www.centre-mersenne.org
e-ISSN : 1778-3569
Comptes Rendus
Mathématique
2022, Vol. 360, p. 1169-1172
https://doi.org/10.5802/crmath.391
Algebra / Algèbre
Procesi’s Conjecture on the
Formanek-Weingarten Function is False
Maciej Dołȩgaa and Jonathan Novak∗, b
a Institute of Mathematics, Polish Academy of Sciences, ul. Śniadeckich 8, 00-956
Warszawa, Poland
b Department of Mathematics, University of California, San Diego, USA
E-mails: mdolega@impan.pl, jinovak@ucsd.edu
Abstract. In this paper, we disprove a recent monotonicity conjecture of C. Procesi on the generating function
for monotone walks on the symmetric group, an object which is equivalent to the Weingarten function of the
unitary group.
Funding. M. D. is supported from Narodowe Centrum Nauki, grant 2021/42/E/ST1/00162/. J. N. is supported
by NSF grant DMS 1812288 and a Lattimer Fellowship.
Manuscript received 30 May 2022, accepted 3 June 2022.
1. Introduction
Let Γd be the Cayley graph of the symmetric group S(d) as generated by the conjugacy class of
transpositions. Thus Γd is a
(d
2
)
-regular graded graph with levels L0, . . . , Ld−1, where Lk is the
set of permutations which factor into a product of d −k disjoint cycles. Let us mark each edge
of Γd corresponding to the transposition (i j ) with j ∈ {2, . . . , d}, the larger of the two symbols
interchanged. This edge labeling was first considered by Stanley [6] and Biane [1] in connection
with noncrossing partitions and parking functions.
A walk on Γd is said to be monotone if the labels of the edges it traverses form a weakly
increasing sequence. The combinatorics of such walks has been intensively studied in recent
years, beginning with the discovery [4] that these trajectories play the role of Feynman diagrams
for integration with respect to Haar measure on unitary groups. This is part of a broader subject
nowadays known as Weingarten calculus, see [2].
Although non-obvious, it is a fact that the number of monotone walks of given length r
between two given permutations ρ,σ ∈ S(d) depends only on the cycle type α ` d of the
permutation ρ−1σ. It is therefore sufficient to consider the number mr (α) of r -step monotone
∗Corresponding author.
ISSN (electronic) : 1778-3569 https://comptes-rendus.academie-sciences.fr/mathematique/
1170 Maciej Dołȩga and Jonathan Novak
walks on Γd beginning at the identity permutation and ending at a fixed permutation of cycle
type α. To each partition α` d we associate the generating function
Mα(x) =
∞∑
r=0
mr (α)xr (1)
enumerating monotone walks on Γd of arbitrary length and type α. It is known [3] that
Mα(x) =
∑
λ`d
χλα∏
∈λ
h () (1− c () x) , (2)
where χλα are the irreducible characters of the symmetric group S(d), with h() and c() being,
respectively, the hook length and content of a given cell  in the Young diagram of λ (see [7]
for definitions). In particular, Mα(x) is a rational function of x which may be considered as a
continuous function of x on the interval (0, 1d−1 ) whose outputs are positive rational numbers.
Up to a simple rescaling, the values Mα(
1
N ) coincide with the values of the Weingarten function
of the unitary group U(N ); see [3, 4].
In a recent paper [5], Procesi has pointed out that the function Mα(x) was also studied from the
perspective of classical invariant theory by Formanek, and that in this context the values Mα(
1
d )
have special significance. Procesi tabulated these numbers for all diagrams α` d ≤ 8, and on the
basis of these computations made the following conjecture.
Conjecture 1. If α>β in lexicographic order, then Mα( 1d ) > Mβ( 1d ).
In this brief note we give explicit numerical examples which show that Conjecture 1 is false.
2. Small x
We first clarify that Procesi’s Conjecture 1 refers to lexicographic order on partitions viewed as
nondecreasing sequences of positive integers, with 1 the first letter in the alphabet, 2 the second
letter, and so on. For example, the partitions of six listed in lexicographic order are
111111
11112
1113
1122
114
123
15
222
24
33
6,
and Conjecture 1 says that the numbers Mα(
1
6 ) strictly decrease as α moves down this list, and
this is so. However, the pattern fails for sufficiently large degree d .
The first sign that Conjecture 1 might be false in general is that it is incompatible with the
known x → 0 asymptotics of Mα(x). The minimal length of a walk on Γd from the identity to
a permutation of type α is d −`(α), and thus by parity the number mr (α) can only be positive
Maciej Dołȩga and Jonathan Novak 1171
when r = d −`(α)+2k with k a nonnegative integer. We may therefore reparameterize the counts
mr (α) as mk (α) := md−`(α)+2k (α) for k ∈N0. The generating function Mα(x) then becomes
Mα(x) = xd−`(α)
∞∑
k=0
mk (α)x
2k . (3)
It is then clear that
lim
x→0
Mβ(x)
Mα(x)
= 0 (4)
whenever `(α) > `(β), which is incompatible with lexicographic order.
One might nevertheless hope that when we compare the small x behavior of Mα(x) and Mβ(x)
with α and β being partitions of the same length, we find compatibility with lexicographic order.
This too is false, as can be seen from the fact [3] that
m0(α) =
`(α)∏
i=1
Catαi−1, (5)
where Catn = 1n+1
(2n
n
)
is the Catalan number. Then forα,β` d partitions of the same length `, we
have
lim
x→0
Mβ(x)
Mα(x)
= ∏̀
i=1
Catβi−1
Catαi−1
. (6)
For small values of d , it does indeed appear to be the case that this product is smaller than 1
when α>β, but this is a law of small numbers. Consider the case where
α=
1,3, . . . , 3︸ ︷︷ ︸
n
 and β=
2, . . . , 2︸ ︷︷ ︸
n
,n +1
 (7)
Then α and β are partitions of the same degree d = 3n +1, they have the same length `(α) =
`(β) = n+1, andα precedes β in the lexicographic order. However, the ratio of the corresponding
Catalan products tends to infinity as n →∞,
Catn
2n
∼ 1p
πn3/2
·2n . (8)
3. Counterexamples
To give a counterexample to Conjecture 1 itself, we return to the character formula (2), which in
fact yields counterexamples if one goes a bit farther than the data tabulated in [5]. Let α+ denote
the successor ofα in the lexicographic order. The first value of d for which Conjecture 1 fails is the
famously unlucky number d = 13, for which there exists precisely one violating pair α,α+. This
pair is
M(16,7)
(
1
13
)
= 13
13
(13!)2
30132115571
1149266300
< 13
13
(13!)2
426729597219
16089728200
= M(15,24)
(
1
13
)
We have tested Conjecture 1 for d ≤ 20 and it fails for all 13 ≤ d ≤ 20. Moreover the size of the
set
Gd :=
{
α` d : Mα
(
1
d
)
< Mα+
(
1
d
)}
of consecutive failures at rank d increases with d . For instance
G14 =
{(
17,7
)
,
(
15,2,7
)
,
(
15,9
)}
,
G15 =
{(
18,7
)
,
(
16,2,7
)
,
(
16,9
)
,
(
14,11
)
,
(
13,2,10
)
,
(
13,3,9
)}
,
G16 =
{(
111,5
)
,
(
19,7
)
,
(
17,2,7
)
,
(
17,9
)
,
(
16,10
)
,
(
15,22,7
)
,
(
15,11
)
,
(
14,2,10
)
,(
14,3,9
)
,
(
13,13
)
, (1,4,11)
}
.
1172 Maciej Dołȩga and Jonathan Novak
Even though Conjecture 1 seems to fail for all d ≥ 13 the structure of the failure set Gd
appears to be very interesting: it seems that when d is large, the points in Gd form many
short lexicographic intervals and one large lexicographic interval. For instance |G20| = 45, so
the proportion of the length of a typical interval on which Mα(
1
|α| ) is monotone is equal to
1
45 .
Nevertheless, for the interval ((1,22,4,11), (2,5,13)], whose cardinality is equal to 151, one has
((1,22,4,11), (2,5,13)]∩G20 = {(2,5,13)}. The number of partitions of size 20 is 627, therefore there
exists an interval on which Mα(
1
|α| ) is monotone and which is more than ten times longer than its
expected length. This suggests that a weaker version of Conjecture 1 might be true. Let Pd denote
the set of partitions of size d .
Question 2. Is it true that there exists constant C > 0 such that for every positive integer d there
exists partitions αd > βd ∈ Pd such that for every lexicographic sequence αd ≥ α > β ≥ βd we
have
Mα
(
1
d
)
> Mβ
(
1
d
)
and
∣∣[αd ,βd ]∣∣
|Pd |
≥C ?
We do not know the answer to this question and we leave it wide open. It would also be
very interesting to find an explicit description of the set Gd , which appears to consists of very
specific partitions which might be classifiable. Even though Conjecture 1 turned out to be false we
believe that the research initiated by Procesi [5] on the behaviour of the function Mα(
1
|α| ) merits
further investigation. Indeed, Procesi’s work has added a new and largely unexplored dimension
to Weingarten calculus.
Acknowledgments
The SageMath computer algebra system has been used for experimentation leading up to the
results presented in the paper.
References
[1] P. Biane, “Parking functions of types A and B”, Electron. J. Comb. 9 (2002), no. 1, article no. N7 (5 pages).
[2] B. Collins, S. Matsumoto, J. Novak, “The Weingarten calculus”, https://arxiv.org/abs/2109.14890, to be pusblished in
Not. Amer. Math. Soc., 2021.
[3] S. Matsumoto, J. Novak, “Jucys–Murphy elements and unitary matrix integrals”, Int. Math. Res. Not. 2013 (2013), no. 2,
p. 362-397.
[4] J. Novak, “Jucys-Murphy elements and the Weingarten function”, in Noncommutative harmonic analysis with appli-
cations to probability. II: Papers presented at the 11th workshop, Bȩdlewo, Poland, August 17–23, 2008, Banach Center
Publications, vol. 89, Polish Academy of Sciences, 2010, p. 231-235.
[5] C. Procesi, “A note on the Formanek Weingarten function”, Note Mat. 41 (2021), no. 1, p. 69-110.
[6] R. P. Stanley, “Parking functions and noncrossing partitions”, Electron. J. Comb. 4 (1997), no. 2, article no. R20
(14 pages).
[7] ——— , Enumerative Combinatorics. Volume 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge
University Press, 1999.


Procesi’s Conjecture on the Formanek-Weingarten Function is False

Adel Alahmadi

Florian Luca

Comptes Rendus
Mathématique
Adel Alahmadi and Florian Luca
There are no Carmichael numbers of the form 2n p +1 with p prime
Volume 360 (2022), p. 1177-1181
https://doi.org/10.5802/crmath.393
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l’édition scientifique ouverte
www.centre-mersenne.org
e-ISSN : 1778-3569
Comptes Rendus
Mathématique
2022, Vol. 360, p. 1177-1181
https://doi.org/10.5802/crmath.393
Number theory / Théorie des nombres
There are no Carmichael numbers of the form
2np +1 with p prime
Adel Alahmadia and Florian Luca∗, b, c , d
a Research Group in Algebraic Structures and its Applications, King Abdulaziz
University, Jeddah, Saudi Arabia
b School of Maths, Wits University, 1 Jan Smuts, Braamfontein 2000, Johannesburg,
South Africa
c Centro de Ciencias Matemáticas, UNAM, Morelia, Mexico
d Research Group in Algebraic Structures and Applications, King Abdulaziz University,
Abdulah Sulayman, Jeddah 22254, Saudi Arabia
E-mails: analahmadi@kau.edu.sa, florian.luca@wits.ac.za
Abstract. In this paper, we prove the theorem announced in the title.
2020 Mathematics Subject Classification. 11A51.
Funding. This project was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University,
Jeddah under grant No. (DF-595-130-1442). The authors gratefully acknowledge DSR technical and financial
support. The second author was also supported by the ANR grant JINVARIANT..
Manuscript received 29 November 2021, revised 11 March 2022, accepted 8 June 2022.
1. Introduction and main result
Primality of numbers of the form 2nk +1 for fixed odd k and varying n has been studied by many
people due to the Proth primality theorem. There are odd numbers k such that 2nk +1 is never
prime for any n. There are infinitely many such odd numbers k. This was proved in 1960 by
Sierpiński and since then such numbers are called Sierpiński numbers in his honor. There are
infinite arithmetic progressions of Sierpiński numbers so certainly such numbers form a subset
of positive lower density of all odd integers. The odd integers k which are not Sierpiński; that is of
the form k = (p−1)/2n for some prime p and nonnegative integer n, also form a subset of positive
lower density of all odd integers. This was proved by Erdős and Odlyzko in [4]. In particular, there
is a subset of odd integers of positive lower density such that k2n +1 is a prime for at least one
n. Presumably, there are odd integers k for which there are infinitely many primes of the form
2nk + 1. This is not known but a quick application of the celebrated Maynard–Tao theorem on
linear forms which are simultaneously primes gives the following.
∗Corresponding author.
ISSN (electronic) : 1778-3569 https://comptes-rendus.academie-sciences.fr/mathematique/
1178 Adel Alahmadi and Florian Luca
Theorem 1. For each K ≥ 1 there are infinitely many odd integers k such that k2n +1 is prime for
at least K values of n. That is, the sequence {k2n +1}n≥1 contains at least K primes.
Since this statement does not seem to have appeared in the literature, we supply a quick proof
of it. Let Li (n) = ai n +bi be distinct be linear forms in the variable n such that ai > 0 and bi are
integers with gcd(ai ,bi ) = 1 for i = 1, . . . , M . The set of linear forms is called admissible if for all
primes p, we have
#
{
0 ≤ n ≤ p −1 : L1(n)L2(n) · · ·LM (n) ≡ 0
(
mod p
)}< p. (1)
For the celebrated Maynard–Tao theorem on primes in simultaneous linear forms we chose the
statement of [5, Theorem 6.4].
Theorem 2 (Maynard–Tao theorem). For any integer K ≥ 2, let M be the smallest integer such
that M log M > e8K+2. Then for any admissible M-tuple of linear forms L1(n), . . . , LM (n) there exist
infinitely many positive integers n such that at least K of L1(n), . . . , LM (n) are primes.
Now for the proof of Theorem 1, let K be fixed, choose M with M log M > e8K+2 and consider
Li (n) = 2(M−1)!i (2n +1)+1 for i = 1, . . . , M . Since L1(n) · · ·LM (n) is a polynomial of degree M in n
the admissibility condition (1) needs to be checked only for primes p ≤ M . Note that Li (n) is odd
for all i = 1, . . . , M . Further, if p ≤ M is odd, then p − 1 | (M − 1)! so by Fermat’s Little Theorem
Li (n) ≡ 2(n + 1) (mod p) for all i = 1, . . . , M . This verifies condition (1), and now Theorem 2
guarantees the existence of infinitely many k’s such that at least K of Li (k) for i = 1, . . . , M are
primes. For such k, the sequence {2n(2k +1)+1}n≥1 contains at least K primes, and in fact, these
K primes all have n ∈ {1,2, . . . , M !}.
A Carmichael number is an odd integer N which is composite but behaves like a prime
with respect to the conclusion of Fermat’s little theorem. Namely, aN ≡ a (mod N ) holds for
all integers a. There are infinitely many Carmichael numbers, a theorem first proved by Alford,
Granville and Pomerance in 1994 in [1]. There is an easy criterion due to Korselt to check whether
N is a Carmichael number. Namely, the composite positive integer N is Carmichael if and only if
N is squarefree and p −1 divides N −1 for all prime factors p of N .
Some authors fixed an odd integer k and asked for Carmichael numbers in the sequence
{2nk +1}n≥1. The results are quite different from the case of primes. There are only finitely many
n such that 2nk +1 is Carmichael and in fact the largest such satisfies
n < 22×107τ(k)2(logk)2ω(k),
where τ(k) and ω(k) are the number of divisors, and the number of prime divisors of k, respec-
tively, and throughout this paper all logs are natural. This is the main theorem in [3]. Letting
K := {k odd : {2nk +1}n≥0 contains some Carmichael number} ,
the set K is of asymptotic density zero (see [2]). The smallest element of K is 27 (see [3,
Theorem 2]), and a representation indicating 27 as a member of K is given by
1729 = 27×26 +1
with the Carmichael number 1729 being known as the Ramanujan taxicab number! In this paper,
we revisit the set K and prove the following maybe somewhat unexpected theorem.
Theorem 3. All members of K are composite.
The statement of the theorem can be rephrased by saying that there is no Carmichael number
of the form 2n p +1 with odd p. Hence, we get the theorem announced in the title.
Adel Alahmadi and Florian Luca 1179
2. The proof
Let λ(n) be the Carmichael function of n. It is the exponent of the multiplicative group modulo
n; namely the smallest positive integer m such that if a is coprime to n, then am ≡ 1 (mod n).
When n is squarefree we have λ(n) = lcm[p −1 : p | n]. Assume by contradiction that p ∈ K for
some odd prime p. By Theorem 2 in [3], we have p ≥ 29. Let N = 2n p+1 be a Carmichael number.
Since λ(N ) | N −1, we get that all prime factors of N are of the form 2mi δi +1 where δi ∈ {1, p}. To
fix notation, we shall assume that
N =
r∏
i=1
(
2mi +1) s∏
j=1
(
2n j p +1) , (2)
where the factors pi = 2mi +1 and q j = 2n j p+1 appearing above are primes. We also assume that
m1 < ·· · < mr (if r > 0) and n1 < ·· · < ns (if s > 0). Thus, r + s =ω(N ) ≥ 3. It is easy to see that both
r > 0, s > 0 must hold. Indeed, if say r = 0, then the only factors that appear in (2) are 2n j p+1 and
the n j ’s are distinct. Expanding and identifying the exact power of 2 dividing N −1, we get n = n1,
which is false since 2n2 | q2 −1 | N −1 = 2n p, so n ≥ n2. A similar contradiction is obtained if one
assumes that s = 0. Hence, both r and s are positive and the argument based on the exponent of
2 appearing in N −1 shows that n1 = m1. This can also be deduced from [6, Theorem 2]. Next, we
show that in fact r ≥ 2. Indeed, if r = 1, we then get
2n p +1 = (2m1 +1) s∏
j=1
(
2n j p +1) ,
which reduced modulo p gives 2m1 ≡ 0 (mod p), a contradiction. We now involve some size
arguments. Let again pi = 2mi +1. Then mi = 2αi for some αi ≥ 0, so pi = Fαi is a Fermat prime.
Here, Fα = 22α +1. [3, Lemma 2] shows that pi < p2. Thus,
r∏
i=1
pi =
r∏
i=1
Fαi ≤
(
Fαr −2
)
Fαr < p2r < p4.
We now look at the q ’s. Let q j = 2n j p + 1. Then 2n j p and 2n p are multiplicatively independent
since p is odd and n j < n. This condition is required in order to apply [3, Lemma 4], which in turn
shows that
n j < 7
√
n log p, (3)
assuming n > 3log p, a hypothesis which we will verify later. Thus, assuming n > 3log p, we get
that
q j < 27
p
n log p p +1 < 27
p
n log p+1.5log p+1, (4)
where we used the fact that 1/log2 < 1.5. We next get an upper bound on s. From the congruences
2n p ≡−1(mod qi ) and 2ni p ≡−1(mod qi ) ,
we get
2n−ni ≡ 1(mod qi ) .
Thus, n − ni is a multiple of ordqi (2), which is the multiplicative order of 2 modulo qi . Since
qi − 1 = 2ni p, we conclude that either p | ordqi (2), or ordqi (2) = 2βi for some βi ≤ ni . To show
that the first possibility must occur, let us assume that the second possibility occurs and get a
contradiction. Since
22
βi ≡ 1(mod 2ni p +1) ,
1180 Adel Alahmadi and Florian Luca
we get that 2βi > ni ≥ n1 = m1 = 2α1 . Hence, βi ≥α1 +1. Further, 2βi | n −ni . Thus, ni = n −2βi ki
for some integer ki . But we have p1 = 22α1 +1 | 2n p +1. Also, p1 | 22α1+1 −1 | 22βi −1. This shows
that
qi = 2ni p +1 = 2n−2
βi ki p +1 = (2n p)(22βi )−ki +1
≡ (−1)×1+1(mod p1) ≡ 0(mod p1) ,
so in fact qi is a multiple of p1, so it cannot be a prime. So, it must be the case that p | ordqi (2),
therefore p | n −ni . Since this is true for all ni , we conclude that ni ≡ n (mod p) are all in the
same residue class modulo p. Since p | n −n1 and n −n1 is nonzero (otherwise q1 = p, which is
false), it follows that n > p. Since p > 3log p holds for p ≥ 29, we are allowed to use inequality (4).
Now since all n j satisfy estimate (3) and are in the same residue class modulo p, we get that the
number of them s satisfies
s ≤ 1+ ns
p
≤ 1+ 7
√
n log p
p
.
Putting everything together and taking logarithms we get
n log2 < log N = log
(
r∏
i=1
pi
)
+ log
(
s∏
j=1
q j
)
< log(p4)+ (7√n log p +1.5log p +1)(1+ 7√n log p
p
)
log2.
Expanding the product in right–hand side and moving the “main term” to the left and keeping
the rest in the right, we get
n
(
1− 49log p
p
)
log2 < 4log p
+
(
7
√
n log p +1.5log p +1+ 7
√
n log p
(
1.5log p +1)
p
)
log2.
Assuming p > 700, the left-hand side exceeds n(log2)/2. Dividing across by n and using n > p
yields
log2
2
< 4log p
p
+ (log2)(7√ log p
p
+ 1.5log p
p
+ 1
p
+ 7
√
log p
(
1.5log p +1)
p3/2
)
,
which gives p < 1700. Indeed the right-hand side above is a decreasing function of p (as a linear
combination with positive coefficients of decreasing functions of p such as log p/p and powers
of it) and when p = 1700 the right-hand side evaluates to 0.345705. . . < 0.346 < (log2)/2. Hence,
22
αr +1 = pr < p2 < 17002,
Adel Alahmadi and Florian Luca 1181
soαr ≤ 4. Thus, the only Fermat primes that might be involved in N are among the first 5 of them,
namely Fα for α ∈ [0,4]. Further, λ(N ) = 2u p for some u ∈ [1,n]. Main Theorem 2 in [6] then gives
that N is one of the numbers
5×13×17,
5×13×193×257,
5×13×193×257×769,
3×11×17,
5×17×29,
5×17×29×113,
5×29×113×65537×114689,
5×17×257×509,
but none of them is of the form 2n p +1 for some prime p. This finishes the argument.
3. Comments
There are a few examples of Carmichael numbers N of the form N = 2n pb +1 for some odd prime
p and positive exponent b > 1 such as
26 ×33 +1, 26 ×36 +1.
Is it true that there are only finitely many Carmichael numbers of this form? If so, we would then
get that ω(N − 1) ≥ 3 holds for all Carmichael numbers N except for finitely many. Are there
infinitely many Carmichael numbers N such that ω(N − 1) = 3? How about ω(N − 1) = 4? Or
maybe ω(N − 1) tends to infinity as N goes to infinity through Carmichael numbers? We leave
such questions for future projects and maybe for future researchers.
Acknowledgements
We thank the referee for constructive comments which improved the quality of our article.
References
[1] W. R. Alford, A. Granville, C. Pomerance, “There are infinitely many Carmichael numbers”, Ann. Math. 139 (1994),
no. 3, p. 703-722.
[2] W. D. Banks, C. Finch, F. Luca, C. Pomerance, P. Stănică, “Sierpiński and Carmichael numbers”, Trans. Am. Math. Soc.
367 (2015), no. 1, p. 355-376.
[3] J. Cilleruelo, F. Luca, A. Pizarro, “Carmichael numbers in the sequence (2n k+1)n≥1”, Math. Comput. 85 (2016), no. 297,
p. 357-377.
[4] P. Erdős, A. M. Odlyzko, “On the density of odd integers of the form (p−1)2−n and related questions”, J. Number Theory
11 (1979), p. 257-263.
[5] A. Granville, “Primes in intervals of bounded length”, Bull. Am. Math. Soc. 52 (2015), no. 2, p. 171-222.
[6] T. Wright, “The impossibility of certain types of Carmichael numbers”, Integers 12 (2012), no. 5, p. 951-964.


There are no Carmichael numbers of the form $2^np+1$ with $p$ prime

Behroz Bidabad

Mir Ahmad Mirshafeazadeh

Harmonic vector fields and the Hodge Laplacian operator on Finsler geometry

Ruoyuan Liu

Tadahiro Oh

On the two-dimensional singular stochastic viscous nonlinear wave equations

Jakub Skrzeczkowski

Fast reaction limit and forward-backward diffusion: A Radon–Nikodym approach

Xiaolong Han

From nodal points to non-equidistribution at the Planck scale

Yann Bugeaud

Fractional parts of powers of real algebraic numbers

Not a member yet