Some Finiteness Results in the Representation Theory of Isometry Groups of Regular Trees

Let G denote the isometry group of a regular tree of degree ≥3. The notion of congruence subgroup is introduced and finite generation of the congruence Hecke algebras is proven. Let U be congruence subgroup and (G; U) be the category of smooth representations of G generated by their U-fixed vectors. We also show that this subcategory is closed under taking subquotients. All these results are analogues of well-known results in the case of p-adic groups. It is also shown that the category of admissible representation of G is Noetherian in the sense that every subrepresentation of a finitely generated admissible representation is again finitely generated. Since we want to emphesize the similarities between these groups and p-adic groups, we give the same proofs which also work in the p-adic case whenever possible.     

Categorical Morita Equivalence for Group-Theoretical Categories

A finite tensor category is called pointed if all its simple objects are invertible. We find necessary and sufficient conditions for two pointed semisimple categories to be dual to each other with respect to a module category. Whenever the dual of a pointed semisimple category with respect to a module category is pointed, we give explicit formulas for the Grothendieck ring and for the associator of the dual. This leads to the definition of categorical Morita equivalence on the set of all finite groups and on the set of all pairs (G, ω), where G is a finite group and ω ? H ³(G, k ^×). A group-theoretical and cohomological interpretation of this relation is given. A series of concrete examples of pairs of groups that are categorically Morita equivalent but have nonisomorphic Grothendieck rings are given. In particular, the representation categories of the Drinfeld doubles of the groups in each example are equivalent as braided tensor categories and hence these groups define the same modular data.     

Category of G-Groups and its Spectral Category

Let G be a group. We analyse some aspects of the category G-Grp of G-groups. In particular, we show that a construction similar to the construction of the spectral category, due to Gabriel and Oberst, and its dual, due to the second author, is possible for the category G-Grp.     

Hereditary triangular matrix comonads

We recognize Harada’s generalized categories of diagrams as a particular case of modules over a monad defined on a finite direct product of additive categories. We work in the dual (albeit formally equivalent) situation, that is, with comodules over comonads. With this conceptual tool at hand, we obtain several of the Harada results with simpler proofs, some of them under more general hypothesis, besides with a characterization of the normal triangular matrix comonads that are hereditary, that is, of homological dimension less than or equal to 1. Our methods rest on a matrix representation of additive functors and natural transformations, which allows us to adapt typical algebraic manipulations from Linear Algebra to the additive categorical setting.     

Weakly group-theoretical and solvable fusion categories

We introduce two new classes of fusion categories which are obtained by a certain procedure from finite groups – weakly group-theoretical categories and solvable categories. These are fusion categories that are Morita equivalent to iterated extensions (in the world of fusion categories) of arbitrary, respectively solvable finite groups. Weakly group-theoretical categories have integer dimension, and all known fusion categories of integer dimension are weakly group-theoretical. Our main results are that a weakly group-theoretical category C has the strong Frobenius property (i.e., the dimension of any simple object in an indecomposable C-module category divides the dimension of C), and that any fusion category whose dimension has at most two prime divisors is solvable (a categorical analog of Burnside's theorem for finite groups). This has powerful applications to classification of fusion categories and semsisimple Hopf algebras of a given dimension. In particular, we show that any fusion category of integer dimension <84 is weakly group-theoretical (i.e. comes from finite group theory), and give a full classification of semisimple Hopf algebras of dimensions pqr and pq², where p,q,r are distinct primes.     

Matrix identities and the pigeonhole principle

We show that short bounded-depth Frege proofs of matrix identities, such as PQ=IQP=I (over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since the latter principle is known to require exponential-size bounded-depth Frege proofs, it follows that the propositional version of the matrix principle also requires bounded-depth Frege proofs of exponential size.     

A geometric perspective on counting non-negative integer solutions and combinatorial identities

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

Recollements arising from cotorsion pairs on extriangulated categories

This paper is devoted to constructing some recollements of additive categories associated to concentric twin cotorsion pairs on an extriangulated category. As an application, this result generalizes the work by W. J. Chen, Z. K. Liu, and X. Y. Yang in a triangulated case [J. Algebra Appl., 2018, 17(5): 1–15]. Moreover, it highlights new phenomena when it applied to an exact category. Finally, we give some applications of our main results. In particular, we obtain Krause's recollement whose proofs are both elementary and very general.     

Cycling in proofs and feasibility

There is a common perception by which small numbers are considered more concrete and large numbers more abstract. A mathematical formalization of this idea was introduced by Parikh (1971) through an inconsistent theory of feasible numbers in which addition and multiplication are as usual but for which some very large number is defined to be not feasible. Parikh shows that sufficiently short proofs in this theory can only prove true statements of arithmetic. We pursue these topics in light of logical flow graphs of proofs (Buss, 1991) and show that Parikh's lower bound for concrete consistency reflects the presence of cycles in the logical graphs of short proofs of feasibility of large numbers. We discuss two concrete constructions which show the bound to be optimal and bring out the dynamical aspect of formal proofs. For this paper the concept of feasible numbers has two roles, as an idea with its own life and as a vehicle for exploring general principles on the dynamics and geometry of proofs. Cycles can be seen as a measure of how complicated a proof can be. We prove that short proofs must have cycles.

     

The Additivity Theorem in K-Theory

We present a method for converting Theorem B style proofs in algebraic K-theory to Theorem A style proofs and apply it to the additivity theorem.     

Spherical functions and integral geometry

The paper presents two proofs of an integral geometric formula concerningn-dimensional ellipsoids. One of the proofs is based on a representation theorem for spherical functions due to Harish-Chandra.     

Equality of proofs for linear equality

This paper is about equality of proofs in which a binary predicate formalizing properties of equality occurs, besides conjunction and the constant true proposition. The properties of equality in question are those of a preordering relation, those of an equivalence relation, and other properties appropriate for an equality relation in linear logic. The guiding idea is that equality of proofs is induced by coherence, understood as the existence of a faithful functor from a syntactical category into a category whose arrows correspond to diagrams. Edges in these diagrams join occurrences of variables that must remain the same in every generalization of the proof. It is found that assumptions about equality of proofs for equality are parallel to standard assumptions about equality of arrows in categories. They reproduce standard categorial assumptions on a different level. It is also found that assumptions for a preordering relation involve an adjoint situation.      

Lower Bounds For Concurrent Zero Knowledge*

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.* An abridge version of this work has appeared in [24].     

Directions for the Long Exact Cohomology Sequence in Moore Categories

A new method for realizing the first and second order cohomology groups of an internal abelian group in a Barr-exact category was introduced by Bourn (Cahiers Topologie Géom Différentielle Catég XL:297–316, 1999; J Pure Appl Algebra 168:133–146, 2002). The main role, in each level, is played by a direction functor. This approach can be generalized to any level n and produces a long exact cohomology sequence. By applying this method to Moore categories we show that they represent a good context for non-abelian cohomology, in particular for the Baer Extension Theory.      

A constructive proof by elementary transformations of Roth's removal theorems in the theory of matrix equations

W. E. Roth gave necessary and sufficient conditions for the existence of solution(s) of certain types of linear matrix equations. Proofs were based on invariant factors and were long and complicated. Other shorter but non-constructive proofs have since been provided by later authors. We present here very brief constructive proofs based on the simplest of mathematical techniques, namely row- and column-reduction of a matrix.     

Normal Sections and Direct Product Decompositions

Abstract

In any finitely complete category, there is an internal notion of normal monomorphism. We give elementary conditions guaranteeing that a normal section s: Y → X of an arrow f: X → Y produces a direct product decomposition of the form X ? Y × W. We then show how these conditions gradually vanish in various algebraic contexts, such as Maltsev, protomodular and additive categories.     

Girth and Euclidean distortion

Let G be a k-regular graph, , with girth g. We prove that every embedding has distortion . Two proofs are given, one based on Markov type [B] and the other on quadratic programming. In the core of both proofs are some Poincaré-type inequalities on graph metrics. Submitted: July 2001, Revised: September 2001.     

On the power of interaction

LetIP[f(n)] be the class of languages recognized by interactive proofs withf(¦x¦) interactions. Babai [2] showed that all languages recognized by interactive proofs with a bounded number of interactions can be recognized by interactive proofs with only two interactions; i.e., for every constantk, IP[k] collapses toIP[2].In this paper, we give evidence that interactive proofs with an unbounded number of interactions may be more powerful than interactive proofs with a bounded number of interactions. We show that for any polynomially bounded polynomial time computable functionf(n) and anyg(n)=o(f(n)) there exists an oracleB such thatIP ^B [f(n)] ₌ IP ^B [g(n)].The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [6], [14] and [10].Research done while in the Department of Mathematics at M. I. T. and supported by an ONR graduate fellowship.Supported in part by NSF Grant DCR MCS8509905.Research done while at the Laboratory for Computer Science at M. I. T. and Supported by an IBM fellowship.     

K-Theory for Triangulated Categories 3 1/2 (A): A Detailed Proof of the Theorem of Homological Functors Dedicated to Daniel Quillen and to the Memory of Robert Thomason

Let A and B be Abelian categories. Let H: A B be a bounded -functor. We prove that H induces a natural map in higher K-theory. From a more precise analysis of the proof, we deduce that it is possible to define a K-theory of the bounded derived category of A, which contains Quillen's K-theory of A as a retract.