This paper introduces new techniques for the efficient computation of discrete Fourier transforms (DFTs) of Sn−k-invariant functions on the symmetric group Sn. We uncover diamond- and leaf-rake-like ...structures in Young's seminormal and orthogonal representations leading to relatively expensive diamond and cheaper leaf-rake computations. These local computations constitute the basis of a reduction/induction process. We introduce a new anticipation technique that avoids diamond computations at the expense of only a small arithmetic overhead for leaf-rake computations. This results in local fast Fourier transforms (FFTs). Combining these local FFTs with a multiresolution scheme close related to the inductive version of Young's branching rule we obtain a global FFT algorithm that computes the DFT of Sn−k-invariant functions on Sn in linear time. More precisely, we show that for fixed k and all n≥2k DFTs of Sn−k-invariant functions on Sn can be computed in at most ck⋅Sn:Sn−k scalar multiplications and additions, where ck denotes a positive constant depending only on k. This run-time is order-optimal and improves Maslen's algorithm.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We study commutative Schur rings over the symplectic groups Sp(n,2) that contain the class C of symplectic transvections. We find the possible partitions of C determined by the Schur ring. We show ...how this restricts the possibilities for multiplicity one subgroups of Sp(n,2).
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We establish a connection between two settings of representation stability for the symmetric groups Sn over C. One is the symmetric monoidal category Rep(S∞) of algebraic representations of the ...infinite symmetric group S∞=⋃nSn, related to the theory of FI-modules. The other is the family of rigid symmetric monoidal Deligne categories Rep_(St), t∈C, together with their abelian versions Rep_ab(St), constructed by Comes and Ostrik.
We show that for any t∈C the natural functor Rep(S∞)→Rep_ab(St) is an exact symmetric faithful monoidal functor, and compute its action on the simple representations of S∞. Considering the highest weight structure on Rep_ab(St), we show that the image of any object of Rep(S∞) has a filtration with standard objects in Rep_ab(St).
As a by-product of the proof, we give answers to the questions posed by P. Deligne concerning the cohomology of some complexes in the Deligne category Rep_(St), and their specializations at non-negative integers n.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let F be a field of characteristic p at least 5. We study the Loewy structures of Specht modules in the principal block of FΣ3p. We show that a Specht module in the block has Loewy length at most 4 ...and composition length at most 14. Furthermore, we classify which Specht modules have Loewy length 1, 2, 3, or 4, produce a Specht module having 14 composition factors, describe the second radical layer and the socle of the reducible Specht modules, and prove that if a Specht module corresponds to a partition that is p-regular and p-restricted then the head of the Specht module does not extend the socle.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We study the remarkable Saxl conjecture which states that tensor squares of certain irreducible representations of the symmetric groups Sn contain all irreducibles as their constituents. Our main ...result is that for sufficiently large n they contain representations corresponding to Young diagrams of hooks, two row and diagrams obtained from hooks and two rows by adding a finite number of squares. For that, we develop a new sufficient condition for the positivity of Kronecker coefficients in terms of characters, and apply this tool using combinatorics of rim hook tableaux in combination with known results on unimodality of certain partition functions. We also present connections and speculations on random characters of Sn.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
New presentations of Specht modules of symmetric groups over fields of characteristic zero have been obtained by Brauner, Friedmann, Hanlon, Stanley and Wachs. These involve generators that are ...column tabloids and relations that are Garnir relations with maximal number of exchanges between consecutive columns or symmetrization of Garnir relations with minimal number of exchanges between consecutive columns. In this paper, we examine Garnir relations and their symmetrization with any number of exchanges. In both cases, we provide sufficient arithmetic conditions so that the corresponding quotient is a Specht module. In particular, in the first case this yields new presentations of Specht modules if the parts of the conjugate partition that correspond to maximal number of exchanges greater than 1 are distinct. These results generalize the presentations mentioned above and offer an answer to a question of Friedmann, Hanlon and Wachs. Our approach is via representations of the general linear group.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
This note provides a set of separating invariants for the ring of vector invariants
of two copies of the natural S
n
-representation
over a field of characteristic 0. This set is much smaller than ...generating sets of
For
we show that this set is minimal with respect to inclusion among all separating sets.
Full text
Available for:
BFBNIB, GIS, IJS, KISLJ, NUK, PNG, UL, UM, UPUK