Submitted works

Advanced search

math.NT — Number Theory

Integrality of iterated averages and pointwise prime powers

Contributed by Darij Grinberg

Suppose that we repeatedly replace the values of an integer-valued function on Z\Z by averages over pp consecutive arguments, where pp is prime. If the first ℓ\ell rounds of averaging give integers, will this remain true when we begin with the ppth powers of the original values? We prove that the answer is yes for ℓ≤p\ell\le p. For p=2p=2 and p=3p=3, the answer is yes for every ℓ\ell, and therefore also when integrality is required at every stage. For larger primes, a known counterexample first fails at round p+1p+1. The proofs use finite differences and polynomial interpolation. We also explain connections with earlier work on divisibility of finite differences and Stirling numbers.

A mix of human-written and AI-generated textHuman understanding: some partsInteger SequencesInteger-valued polynomialsdivisibilityfinite differencessupercongruences
Oct 29, 202629 pages
PDFView work

math.CO — Combinatorics

The Anti-Arithmetic Product of Symmetric Functions

Contributed by Darij Grinberg

The \emph{arithmetic product} ⊡\boxdot is a bilinear operation on the ring of symmetric functions over Q\mathbb Q defined by \[ p_\lambda \ \boxdot\ p_\mu = \prod_{i,j}p_{\operatorname{lcm}(\lambda_i,\mu_j)}^{\gcd(\lambda_i,\mu_j)} \] on the power-sum basis (pλ)(p_\lambda). It is known that this operation preserves the subring SymmZ\mathbf{Symm}_{\mathbb Z} of symmetric functions with integer coefficients, and is Schur-positive on pairs of Schur functions. Indeed, it corresponds to induction of representations from Sn×SmS_n \times S_m to SnmS_{nm}. In this work, we consider the \emph{anti-arithmetic product} ♢\diamondsuit, which is defined by the same formula but with gcd⁡\gcd and lcm⁡\operatorname{lcm} interchanged. We show that it, too, preserves SymmZ\mathbf{Symm}_{\mathbb Z}, even though it lacks the Schur positivity property. This was conjectured on MathOverflow in 2014. Our method is a more intricate variant of the representation-theoretical interpretation of ⊡\boxdot. The anti-arithmetic product does not correspond to an operation on actual representations; but its adjoint can still be described as a map on characters, which (as we show) is a λ\lambda-ring morphism from the character ring of SmnS_{mn} to that of Sm×SnS_m \times S_n. Now, a 1975 theorem of Boorman shows that the representation ring of SnS_n is generated by the natural permutation representation Mn=QnM_n = \mathbb Q^n as a λ\lambda-ring. Thus, the proof of integrality boils down to only computing the image of MmnM_{mn} under this adjoint, which can be done using M\"obius inversion in the representation ring. This work is aimed at readers familiar with representation rings and the representation theory of symmetric groups. No prior knowledge of λ\lambda-rings is presumed. Three self-contained proofs of Boorman's theorem are given in the appendices, two of them lifting the theorem to the noncommutative symmetric functions (or Solomon's descent algebra), recovering a result of Schocker.

A mix of human-written and AI-generated textHuman understanding: all partsSpecht modulesdescent algebralambda-ringsnoncommutative symmetric functionssymmetric functionssymmetric group representations
Oct 03, 202650 pages
PDFView work

math.CO — Combinatorics

Collapsibility of Alexander duals for shade maps

Contributed by Darij Grinberg

Let EE be a nonempty finite set. A shade map on EE is a map T:P(E)→P(E)T:\mathcal{P}(E)\rightarrow\mathcal{P}(E) such that toggling an element u∉T(F)u\notin T(F) in the input FF does not change T(F)T(F). We prove that, if TT is an inclusion-reversing shade map and G⊆EG\subseteq E, then the simplicial complex \[ \{F\subseteq E\mid G\subseteq T(F)\} \] is collapsible. Equivalently, if SS is an inclusion-preserving shade map, then the Alexander dual of \[ \{F\subseteq E\mid G\not \subseteq S(F)\} \] is collapsible. This is an Alexander-dual companion to the shade-map collapsibility theorem in \emph{The Elser nuclei sum revisited}. The proof first matches all faces on which T(F)≠ET(F)\neq E by a toggle. The remaining faces, characterized by T(F)=ET(F)=E, form the free convex set complex of an associated antimatroidal quasi-closure operator. We give a self-contained recursive acyclic matching on this complex. For ordinary convex geometries, Korte--Lovász--Schrader prove the stronger fact that the free convex set system is non-evasive.

A mix of human-written and AI-generated textHuman understanding: all partsantimatroidsconvex geometriesdiscrete Morse theorygraphssimplicial complexes
Sep 30, 202618 pages
PDFView work

math.CO — Combinatorics

On a non-basis of the coinvariant algebra

Contributed by Darij Grinberg

A conjecture arising from a question of Procesi proposes a basis of the coinvariant algebra of SnS_n consisting of column-antisymmetrized monomials indexed by pairs of standard Young tableaux. We show that the proposed family need not even span an SnS_n-subrepresentation: for n=8n=8, a generator of degree 1515 is sent outside the span by the adjacent transposition (4,5)(4,5). The proof is an exact finite computation with an explicit separating functional, requiring neither a rank computation nor Gr\"obner reduction. We also retain an explicit relation for n=7n=7, where the basis assertion first fails, although the span is still invariant.

A mix of human-written and AI-generated textHuman understanding: all partsSpecht modulesYoung tableauxcoinvariant algebrahigher Specht polynomialsrepresentations of the symmetric group
Sep 29, 202626 pages
PDFView work

math.RA — Rings and Algebras

A Universal Noncommutative Splitting Algebra for Polynomials

Contributed by Darij Grinberg

Let RR be a commutative ring. We show that every homogeneous polynomial f∈R[x1,…,xm]f\in R[x_{1},\ldots,x_{m}] of degree nn splits into a product of nn homogeneous linear forms over a suitable noncommutative ring extension SS of RR (that is, over a noncommutative RR-algebra SS whose structure morphism R→SR\rightarrow S is injective). The algebra SS is universal for such factorizations and is free as an RR-module. The proof uses Bergman's Diamond Lemma: we define SS by generators and relations, and the relations form a terminating reduction system that has no ambiguities and thus is confluent. An analogous result is also shown for inhomogeneous polynomials (with inhomogeneous factors). This easily follows from the homogeneous case by homogenizing and then setting the homogenizing variable equal to 11.

A mix of human-written and AI-generated textHuman understanding: all partsBergman's diamond lemmaGröbner basescombinatorial algebranoncommutative polynomials
Sep 29, 202610 pages
PDFView work

math.CO — Combinatorics

A counterexample to the Burman--Kulishov conjecture on Lie elements

Contributed by Darij Grinberg

Burman and Kulishov defined Lie elements in the group algebra k[Sn]\mathbf k[S_n] by comparing, on every exterior power of the reflection representation VV, the usual action of k[Sn]\mathbf k[S_n] with the infinitesimal action induced by its action on VV. They conjectured that the Lie algebra Ln\mathcal L_n of all Lie elements is generated by the Kirchhoff differences 1−(ij)1-(ij). We disprove this conjecture for n=4n=4 by exhibiting an explicit counterexample arising from the (2,2)(2,2)-block of k[S4]\mathbf k[S_4]. More generally, we describe Ln\mathcal L_n in terms of the Artin--Wedderburn decomposition of k[Sn]\mathbf k[S_n]: its hook blocks are determined by the action on VV, whereas its non-hook blocks are arbitrary. Consequently, the primitive central idempotents of the non-hook blocks yield linearly independent obstructions to the conjecture. We also identify the Lie algebra generated by the Kirchhoff differences in terms of the derived algebra of the Lie algebra generated by transpositions. Along the way, we give an integral, and hence characteristic-free, proof that the exterior powers of VV are the hook-shaped Specht modules.

A mix of human-written and AI-generated textHuman understanding: all partsLie algebrasymmetric group algebrasymmetric group representations
Sep 29, 202615 pages
PDFView work

math.AC — Commutative Algebra

Polynomials over Symmetric Polynomials

Contributed by Darij Grinberg

Let k\mathbf{k} be a commutative ring, and let the symmetric group Sn\mathfrak{S}_{n} act on $P=\mathbf{k}\left[ x_{1} ,x_{2},\ldots,x_{n} \right] $ by permuting the variables. We prove four results that are known (at least in the case when k\mathbf{k} is a field) but not easily found in the literature. First, the coinvariant algebra (the quotient of PP by the ideal generated by the symmetric polynomials with constant term 00) is a free k\mathbf{k}-module of rank n!n!, with the residue classes of the Artin monomials as a basis. Second, PP is a free module of rank n!n! over the ring PSnP^{\mathfrak{S}_{n}} of symmetric polynomials, again with the Artin monomials as a basis. Third, if n!n! is invertible in k\mathbf{k}, the coinvariant algebra is the regular $\mathbf{k}\left[ \mathfrak{S}_{n} \right] $-module. Fourth, under the same hypothesis, PP is a free left PSn[Sn]P^{\mathfrak{S}_{n}}\left[ \mathfrak{S}_{n} \right] -module of rank 11. The first result follows from an elementary normal-form lemma for monic polynomials with pairwise relatively prime leading monomials. The second is proved by lifting the Artin basis. For the third, we use orbit harmonics with a strongly discrete point orbit, and the fourth follows by equivariantly lifting a regular basis of the coinvariant algebra.

A mix of human-written and AI-generated textHuman understanding: all partsArtin basisGröbner basescoinvariant algebraorbit harmonicssymmetric polynomials
Sep 28, 202629 pages
PDFView work

math.CO — Combinatorics

A counterexample to ordering-independence for chromatic operators

Contributed by Darij Grinberg

We give a 1010-vertex counterexample to a conjecture of Pawlowski asserting that the characteristic polynomial of a chromatic operator associated with a forest is independent of the ordering of its edges. The two operators already have different traces of fifth powers.

Primarily AI-generated textHuman understanding: all partsGraph coloringSpecht modulessymmetric group algebra
Sep 28, 20265 pages
PDFView work

math.AC — Commutative Algebra

Splitting a Polynomial into Linear Factors after an Injective Ring Extension

Contributed by Darij Grinberg

We show that each univariate polynomial P=p0+p1X+⋯+pmXm∈R[X]P = p_0 + p_1 X + \cdots + p_m X^m \in R[X] over a commutative ring RR can be factored into linear factors over a suitable commutative ring extension SS of RR. The proof proceeds by universal construction: SS is defined as the tensor product R⊗CmBmR \otimes_{C_m} B_m, where BmB_m is the polynomial ring $\ZZ[a_1, b_1, a_2, b_2, \ldots, a_m, b_m]$, and where CmC_m is its subring generated by its ``homogenized elementary symmetric polynomials'' Er=∑I⊆[m];∣I∣=r∏i∈Iai∏i∉IbiE_r=\sum_{\substack{I\subseteq [m];\\ |I|=r}} \prod_{i\in I}a_i\prod_{i\notin I}b_i for all 0≤r≤m0 \leq r \leq m. The injectivity of the structure homomorphism R→SR \to S is deduced from a combinatorial study of the diagonal subring of BmB_m. In the process, a homogeneous variant of the Garsia--Stanton basis is constructed, and some classical properties of symmetric polynomials are recovered.

A mix of human-written and AI-generated textHuman understanding: all parts
Sep 28, 202629 pages
PDFView work

math.CO — Combinatorics

A Counterexample to a Conjecture on Fused Specht Polynomials

Contributed by Darij Grinberg

Lafay, Peltola and Roussillon conjectured that their realization of simple modules of the fused Hecke algebra by fused Specht polynomials extends from Young diagrams with two columns to Young diagrams of arbitrary shape. We give a counterexample for \[ n=8,\qquad \lambda=(3,2,2,1),\qquad \varsigma=(2,2,2,2). \] More precisely, we exhibit an explicit linear dependence among three fused Specht polynomials indexed by row-strict Young tableaux. The same example also yields an infinite family of counterexamples.

Primarily AI-generated textHuman understanding: some partsSpecht modulesSpecht polynomialsYoung tableaux
Sep 28, 20263 pages
PDFView work