Uniformly generated submodules of permutation modules: Over fields of characteristic 0

This paper is motivated by a link between algebraic proof complexity and the representation theory of the finite symmetric groups. Our perspective leads to a new avenue of investigation in the representation theory of S_n. Most of our technical results concern the structure of “uniformly” generated submodules of permutation modules. For example, we consider sequences of submodules of the permutation modules M^(n−k,1k) and prove that if the sequence W_n is given in a uniform (in n) way – which we make precise – the dimension p(n) of W_n (as a vector space) is a single polynomial with rational coefficients, for all but finitely many “singular” values of n. Furthermore, we show that dim(W_n)<p(n) for each singular value of n≥4k. The results have a non-traditional flavor arising from the study of the irreducible structure of the submodules W_n beyond isomorphism types. We sketch the link between our structure theorems and proof complexity questions, which are motivated by the famous NP vs. co-NP problem in complexity theory. In particular, we focus on the complexity of showing membership in polynomial ideals, in various proof systems, for example, based on Hilbert's Nullstellensatz.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

Fragments of Arithmetic and true sentences

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Π_n+1‐sentences true in the standard model is the only (up to deductive equivalence) consistent Π_n+1‐theory which extends the scheme of induction for parameter free Π_n+1‐formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first‐order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain results on the quantifier complexity, (non)finite axiomatizability and relative strength of schemes for Δ_n+1‐formulas. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the length of subgroup chains in the symmetric group

We prove that for n≥2, the length of every subgroup chain in S_n is at most 2n-3. The proof rests on an upper bound for the order of primitive permutation groups, due to Praeger and Saxl. The result has applications to worst case complexity estimates for permutation group algorithms.     

Translation Lengths in Out(F n)

We prove that all elements of infinite order in Out(F _n) have positive translation lengths; moreover, they are bounded away from zero. As a consequence we get a new proof that solvable subgroups of Out(F _n) are finitely generated and virtually Abelian.     

On the order of doubly transitive permutation groups

Our aim is to contribute to an old problem of group theory. We prove that the order of a doubly transitive permutation group of degreen other thanA _n orS _n is less than exp exp . The best bound previously known was 4 ⁿ (published in 1980). The proof is based on results of A. Bochert (1892) and H. Wielandt (1934) and uses combinatorial techniques.Dedicated to Alfred Bochert and Helmut Wielandt     

The small‐is‐very‐small principle

The central result of this paper is the small‐is‐very‐small principle for restricted sequential theories. The principle says roughly that whenever the given theory shows that a definable property has a small witness, i.e., a witness in a sufficiently small definable cut, then it shows that the property has a very small witness: i.e., a witness below a given standard number. Which cuts are sufficiently small will depend on the complexity of the formula defining the property. We draw various consequences from the central result. E.g., roughly speaking, (i) every restricted, recursively enumerable sequential theory has a finitely axiomatized extension that is conservative with respect to formulas of complexity $\le n$; (ii) every sequential model has, for any n, an extension that is elementary for formulas of complexity $\le n$, in which the intersection of all definable cuts is the natural numbers; (iii) we have reflection for ${\mathrm{\Sigma }}_2^0$‐sentences with sufficiently small witness in any consistent restricted theory U; (iv) suppose U is recursively enumerable and sequential. Suppose further that every recursively enumerable and sequential V that locally inteprets U, globally interprets U. Then, U is mutually globally interpretable with a finitely axiomatized sequential theory. The paper contains some careful groundwork developing partial satisfaction predicates in sequential theories for the complexity measure depth of quantifier alternations.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

The Pre-WDVV Ring of Physics and its Topology

We show how a simplicial complex arising from the WDVV (Witten-Dijkgraaf-Verlinde-Verlinde) equations of string theory is the Whitehouse complex. Using discrete Morse theory, we give an elementary proof that the Whitehouse complex Δ_n is homotopy equivalent to a wedge of (n−2)! spheres of dimension n−4. We also verify the Cohen-Macaulay property. Additionally, recurrences are given for the face enumeration of the complex and the Hilbert series of the associated pre-WDVV ring. 2000 Mathematics Subject Classification: Primary—13F55, Secondary—05E99, 55P15     

On the Diaconis-Shahshahani Method in Random Matrix Theory

If Γ is a random variable with values in a compact matrix group K, then the traces Tr(Γ^j) (j ∊ N) are real or complex valued random variables. As a crucial step in their approach to random matrix eigenvalues, Diaconis and Shahshahani computed the joint moments of any fixed number of these traces if Γ is distributed according to Haar measure and if K is one of U_n, O_n or Sp_n, where n is large enough. In the orthogonal and symplectic cases, their proof is based on work of Ram on the characters of Brauer algebras. The present paper contains an alternative proof of these moment formulae. It invokes classical invariant theory (specifically, the tensor forms of the First Fundamental Theorems in the sense of Weyl) to reduce the computation of matrix integrals to a counting problem, which can be solved by elementary means.     

The crossing number of Cm × Cn is as conjectured for n ≥ m(m + 1)

It has been long conjectured that the crossing number of C_m × C_n is (m?2)n, for all m, n such that n ≥ m ≥ 3. In this paper, it is shown that if n ≥ m(m + 1) and m ≥ 3, then this conjecture holds. That is, the crossing number of C_m × C_n is as conjectured for all but finitely many n, for each m. The proof is largely based on techniques from the theory of arrangements, introduced by Adamsson and further developed by Adamsson and Richter. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 53–72, 2004     

Cayley’s decomposition and pólya’sW-property of ordinary linear differential equations

A proof is given for the equivalence of Pólya’sW- property of a linear differential equationL _n (D) y=0 to the possibility of decomposingL _n (D) ≡ Π _n ¹ [D+λ_i(x)] in a given interval. In this case a set ofn independent solutions form a Chebyshev system in the interval. An application determines intervals of non-oscillation for solutions of linear equations of the second order. Research supported by the National Science Foundation Grant No. GP-3897 with the University of Maryland.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

Property A in an Infinite-Dimensional Space. I

   Abstract. We prove that an infinite-dimensional space of piecewise polynomial functions of degree at most n-1 with infinitely many simple knots, n ≥ 2 , satisfies Property A. Apart from its independent interest, this result allows us to solve an open classical problem (n ≥ 3 ) in theory of best approximation: the uniqueness of best L ₁ -approximation by n -convex functions to an integrable, continuous function defined on a bounded interval. In this first part of the paper we prove the case n=2 and give key results in order to complete the general proof in the second part.     

The unramified computation of Rankin-Selberg integrals for SO2l × GLn

Let SO _2l be the special orthogonal group, either split or quasi-split over a number field, and 1 < l < n. We compute the local integral, where data are unramified, derived from the global Rankin-Selberg construction for SO _2l × GL _n . In the general case, the local integral is difficult to compute directly, so instead it is transformed to an integral related to a construction for SO _2n+1×GL _n , which carries a Bessel model on SO _2n+1. For the quasisplit case, when l = n − 1 we are able to compute the local integral, by a modification of our recently introduced approach using invariant theory. This leads to another proof of our result for 1 < l < n, as well as a new proof of a known result regarding the unramified Bessel function.     

Une preuve simple des conjectures de Langlands pour GL(n) sur un corps p-adique

Let F be a finite extension of ℚ _p . For each integer n≥1, we construct a bijection from the set ?_F ⁰ (n) of isomorphism classes of irreducible degree n representations of the (absolute) Weil group of F, onto the set ? _F ⁰ (n) of isomorphism classes of smooth irreducible supercuspidal representations of GL _n (F). Those bijections preserve epsilon factors for pairs and hence we obtain a proof of the Langlands conjectures for GL _n over F, which is more direct than Harris and Taylor’s. Our approach is global, and analogous to the derivation of local class field theory from global class field theory. We start with a result of Kottwitz and Clozel on the good reduction of some Shimura varieties and we use a trick of Harris, who constructs non-Galois automorphic induction in certain cases. Oblatum 1-III-1999 & 21-VII-1999 / Published online: 29 November 1999     

On the Faith-Utumi theorem

In this paper we shall give a new proof of the well-known theorem of Faith-Utumi^[1]. Using our method we can show that every right order ofK _n is a prime right Goldie ring, whereK _n is the n×n-matrix ring over division ring K. Specially,D _n is a prime right Goldie ring, ifD is a right order ofK.The Project Supported by the National Natural Science Foundation of China.     

Algorithms for ham-sandwich cuts

Given disjoint setsP ₁,P ₂, ...,P _d inR ^d withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP _i . We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR ^d−1 . With the current estimates, we get complexity close toO(n ^3/2 ) ford=3, roughlyO(n ^8/3 ) ford=4, andO(n ^d−1−a(d) ) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR ³ when the three sets are suitably separated. A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

On the number of subgroups of given index in the modular group

A new recurrence for the number of subgroups of given index in the modular group is derived. The proof requires the derivation of a recurrence for a sequencea _nb_n from recurrences for thea _n andb _n. We show that this is always possible if thea _n andb _n satisfy polynomial recurrences. We also include a short proof of a result ofW. W. Stothers on the parity of the number of subgroups of given index in the modular group.