Vaguery + group-theory   62

Multiplying Non-Numbers
In last last week's episode of PBS Infinite Series, we talked about different flavors of multiplication (like associativity and commutativity) to think about when multiplying things that aren't numbers. My examples of multiplying non-numbers were vectors and matrices, which come from the land of algebra. Today I'd like to highlight another example:
8 days ago by Vaguery
The Sum-Product Problem Shows How Addition and Multiplication Constrain Each Other | Quanta Magazine
In 1983 the prolific conjecturer Paul Erdős posed a math problem: Take any set of numbers you like. These could be the whole numbers from 1 to 12, the first 10,000 prime numbers, or the dates of every birthday in your extended family. Arrange these numbers in a square grid, with your list of numbers arranged both across the bottom and up one side. Then fill in the grid with either the sums or the products of the crosswise pairs.
mathematical-recreations  number-theory  rather-interesting  open-questions  group-theory  to-understand  hypergraphs
april 2019 by Vaguery
[1808.00722] On the Harborth constant of $C_3 oplus C_{3n}$
For a finite abelian group (G,+,0) the Harborth constant 𝗀(G) is the smallest integer k such that each squarefree sequence over G of length k, equivalently each subset of G of cardinality at least k, has a subsequence of length exp(G) whose sum is 0. In this paper, it is established that 𝗀(G)=3n+3 for prime n≠3 and 𝗀(C3⊕C9)=13.
december 2018 by Vaguery
[1808.08697] Universal groups of cellular automata
We prove that the group of reversible cellular automata (RCA), on any alphabet A, contains a perfect subgroup generated by six involutions which contains an isomorphic copy of every finitely-generated group of RCA on any alphabet B. This result follows from a case study of groups of RCA generated by symbol permutations and partial shifts with respect to a fixed Cartesian product decomposition of the alphabet. For prime alphabets, we show that this group is virtually cyclic, and that for composite alphabets it is non-amenable. For alphabet size four, it is a linear group. For non-prime non-four alphabets, it contains copies of all finitely-generated groups of RCA. We also obtain that RCA of biradius one on all large enough alphabets generate copies of all finitely-generated groups of RCA. We ask a long list of questions.
group-theory  cellular-automata  rewriting-systems  reversible  open-questions  to-write-about  to-understand
december 2018 by Vaguery
[math/0408099] Tropical Mathematics
These are the notes for the Clay Mathematics Institute Senior Scholar Lecture which was delivered by Bernd Sturmfels in Park City, Utah, on July 22, 2004. The topic of this lecture is the tropical approach'' in mathematics, which has gotten a lot of attention recently in combinatorics, algebraic geometry and related fields. It offers an an elementary introduction to this subject, touching upon Arithmetic, Polynomials, Curves, Phylogenetics and Linear Spaces. Each section ends with a suggestion for further research. The bibliography contains numerousreferences for further reading in this field.
group-theory  mathematics  representation  combinatorics  rather-interesting  to-write-about
october 2018 by Vaguery
[1808.03172] An Invitation to Noncommutative Algebra
This is a brief introduction to the world of Noncommutative Algebra aimed for advanced undergraduate and beginning graduate students.
mathematics  to-read  to-understand  group-theory  category-theory  introduction
august 2018 by Vaguery
More Secrets of the Associahedra | The n-Category Café
The associahedra are wonderful things discovered by Jim Stasheff around 1963 but even earlier by Dov Tamari in his thesis. They hold the keys to understanding ‘associativity up to coherent homotopy’ in exquisite combinatorial detail.

But do they still hold more secrets? I think so!
group-theory  mathematical-recreations  open-questions  symmetry  to-write-about  to-understand  consider:visual-algorithms
february 2018 by Vaguery
[1709.07504] Hopf monoids and generalized permutahedra
Generalized permutahedra are a family of polytopes with a rich combinatorial structure and strong connections to optimization. We prove that they are the universal family of polyhedra with a certain Hopf algebraic structure. Their antipode is remarkably simple: the antipode of a polytope is the alternating sum of its faces. Our construction provides a unifying framework to organize numerous combinatorial structures, including graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, building sets, and simple graphs. We highlight three applications: 1. We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give the optimal formula for the antipode of graphs, posets, matroids, hypergraphs, and building sets, and we answer questions of Humpert--Martin and Rota. 2. We show that the reciprocity theorems of Stanley and Billera--Jia--Reiner on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of the same reciprocity theorem for generalized permutahedra. 3. We explain why the formulas for the multiplicative and compositional inverses of power series are governed by the face structure of permutahedra and associahedra, respectively, answering a question of Loday. Along the way, we offer a combinatorial user's guide to Hopf monoids.
combinatorics  group-theory  to-understand  rather-interesting
january 2018 by Vaguery
Welcome to GF(4) – The Math Citadel
Notice that this solution is not the same as when we lived in our comfortable world of real numbers. The equations were the same, the numbers involved were the same, but we changed what addition and multiplication did by moving to a new field called GF(4). The purpose of this exercise was to get used to the idea of arithmetic in a new space, and to see what an example of a Galois field looks like. Explaining how to generate these Galois fields in general and defining their addition and multiplication tables will get a bit involved; we’ll tackle these soon. For now, it’s important just to let go of our tightly held arithmetic notions that are really special properties of real numbers. Systems of equations can yield different solutions when we move to a new world.
mathematics  heuristics  mathematical-recreations  to-write-about  group-theory  rather-interesting
december 2017 by Vaguery
This document contains the notes of a lecture I gave at the "Journ\'ees Nationales du Calcul Formel" (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for p-adic numbers. It is divided into two main parts: first, we present various implementations of p-adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations.
number-theory  rather-interesting  algorithms  group-theory  nudge-targets  consider:representation  consider:looking-to-see
april 2017 by Vaguery
[1605.06937] Diagrammatic approach to cellular automata and the emergence of form with inner structure
We present a diagrammatic method to build up sophisticated cellular automata (CAs) as models of complex physical systems. The diagrams complement the mathematical approach to CA modeling, whose details are also presented here, and allow CAs in rule space to be classified according to their hierarchy of layers. Since the method is valid for any discrete operator and only depends on the alphabet size, the resulting conclusions, of general validity, apply to CAs in any dimension or order in time, arbitrary neighborhood ranges and topology. We provide several examples of the method, illustrating how it can be applied to the mathematical modeling of the emergence of order out of disorder. Specifically, we show how the the majority CA rule can be used as a building block to construct more complex cellular automata in which separate domains (with substructures having different dynamical properties) are able to emerge out of disorder and coexist in a stable manner.
cellular-automata  formalization  automata  group-theory  to-understand  classification
june 2016 by Vaguery
[1605.01721] $E_8$, the most exceptional group
The five exceptional simple Lie algebras over the complex number are included one within the other as G2⊂F4⊂E6⊂E7⊂E8. The biggest one, E8, is in many ways the most mysterious. This article surveys what is known about it including many recent results, focusing on the point of view of Lie algebras and algebraic groups over fields.
algebra  group-theory  review  to-understand
may 2016 by Vaguery
[1602.08028] Features of a high school olympiad problem
This paper is a supplement to a talk for mathematics teachers given at the 2016 LSU Mathematics Contest for High School Students. The paper covers more details and aspects than could be covered in the talk.
We start with an interesting problem from the 2009 Iberoamerican Math Olympiad concerning a particular sequence. We include a solution to the problem, but also relate it to several areas of mathematics. This problem demonstrates the countability of the rational numbers with a direct one-to-one correspondence. The problem also shows the one-to-one correspondence of finite continued fractions and rational numbers. The subsequence of odd indexed terms was constructed by Johannes Kepler and is discussed. We also show that the indices have an extension to the 2-adic integers giving a one-to-one correspondence between the positive real numbers and the 2-adic integers. Everything but the extension to the 2-adic integers is known to have appeared elsewhere.
continued-fractions  algebra  mathematical-recreations  number-theory  group-theory  nudge-targets  consider:looking-to-see
april 2016 by Vaguery
[1507.02762] A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(nlog2n)-time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n18)-time algorithm of Keating and Vince and generalizes recent work by Brlek, Proven\c{c}al, F\'{e}dou, and the second author.
tiling  group-theory  symmetry  rather-interesting  proof  computational-geometry  nudge-targets  consider:rediscovery
april 2016 by Vaguery
[1506.02797] Abelian Powers and Repetitions in Sturmian Words
Richomme, Saari and Zamboni (J.~Lond.~Math.~Soc.~83:~79--95,~2011) proved that at every position of a Sturmian word starts an abelian power of exponent k for every k>0. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period m starting at a given position in any Sturmian word of rotation angle α. vAs an analogue of the critical exponent, we introduce the abelian critical exponent A(sα) of a Sturmian word sα of angle α as the quantity A(sα)=limsup km/m=limsup k′m/m, where km (resp. k′m) denotes the maximum exponent of an abelian power (resp.~of an abelian repetition) of abelian period m (the superior limits coincide for Sturmian words). We show that A(sα) equals the Lagrange constant of the number α. This yields a formula for computing A(sα) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A(sα)≥5‾√ and that the equality holds for the Fibonacci word. We further prove that A(sα) is finite if and only if α has bounded partial quotients, that is, if and only if sα is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period Fj, j>1, has length Fj(Fj+1+Fj−1+1)−2 if j is even or Fj(Fj+1+Fj−1)−2 if j is odd, where Fj is the jth Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words.
group-theory  rewriting-systems  mathematics  representation  rather-interesting  consider:rediscovery  consider:representation  nudge-targets
april 2016 by Vaguery
[1412.1457] Remark on Continued Fractions, Moebius Transformations and Cycles
In a recent paper A.Beardon and I.Short proposed to use chains of tangent horocycles as an extended tool describing continued fractions. We review the origin of such construction from the Moebius transformations point of view. Related descriptions with chains of orthogonal horocycles emerged as a result. The approach is extended to several dimensions in a way which is compatible to the early proposition of A.Beardon based on Clifford algebras.
continued-fractions  mathematics  group-theory  number-theory  nudge-targets  consider:looking-to-see
april 2016 by Vaguery
[1505.06581] Simple permutations with order $4n + 2$ by means of Pasting and Reversing
The problem of genealogy of permutations has been solved partially by Stefan (odd order) and Acosta-Hum\'anez \& Bernhardt (power of two). It is well known that Sharkovskii's theorem shows the relationship between the cardinal of the set of periodic points of a continuous map, but simple permutations will show the behaviour of those periodic points. Recently Abdulla et al studied the structure of minimal 4n+2-orbits of the continuous endomorphisms on the real line. This paper studies some combinatorial dynamics structures of permutations of mixed order 4n+2, describing its genealogy, using Pasting and Reversing.
dynamical-systems  rewriting-systems  group-theory  nudge-targets  consider:instruction-set
march 2016 by Vaguery
[1209.4598] Pasting and Reversing Operations over some Vector Spaces
Pasting and Reversing operations have been used successfully over the set of integer numbers, simple permutations, rings and recently over a generalized vector product. In this paper, these operations are defined from a natural way to be applied over vector spaces. In particular we study Pasting and Reversing over vectors, matrices and we rewrite some properties for polynomials as vector space. Finally we study some properties of Reversing through linear transformations as for example an analysis of palindromic and antipalindromic vector subspaces.
oh-yeah  algebra  linear-algebra  out-of-the-box  nudge-targets  group-theory  consider:looking-to-see
march 2016 by Vaguery
[1010.1967] On Pasting and Reversing operations over some rings
In this paper we study two operations, Pasting and Reversing, defined from a natural way to be applied over some rings such as the ring of polynomials and the ring of linear differential operators, which is a differential ring. We obtain some properties of these operations over these rings, in particular over the set of natural numbers, in where we rewrite some properties incoming from recreational mathematics.
oh-yeah  group-theory  algebra  mathematics  rather-interesting  out-of-the-box  nudge-targets
march 2016 by Vaguery
[1603.07065] Pasting and Reversing Approach to Matrix Theory
The aim of this paper is to study some aspects of matrix theory through Pasting and Reversing. We start giving a summary of previous results concerning to Pasting and Reversing over vectors and matrices, after we rewrite such properties of Pasting and Reversing in matrix theory using linear mappings to finish with new properties and new sets in matrix theory involving Pasting and Reversing. In particular we introduce new linear mappings: Palindromicing and Antipalindromicing mappings, which allow us to obtain palindromic and antipalindromic vectors and matrices.
oh-yeah  matrices  out-of-the-box  group-theory  algebra  nudge-targets  consider:rediscovery  consider:doing-this-asap
march 2016 by Vaguery
[1603.07271] Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem
We introduce cellular automata whose cell spaces are left homogeneous spaces and prove a uniform as well as a topological variant of the Curtis-Hedlund-Lyndon theorem. Examples of left homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations.
cellular-automata  formal-languages  group-theory  out-of-the-box  nudge-targets  consider:looking-to-see
march 2016 by Vaguery
[1602.06372] Convex Polygons for Aperiodic Tiling
If all tiles in a tiling are congruent, the tiling is called monohedral. Tiling by convex polygons is called edge-to-edge if any two convex polygons are either disjoint or share one vertex or one entire edge in common. We find that a convex polygon that can generate an edge-to-edge monohedral tiling must be able to generate a periodic tiling.
tiling  proof  plane-geometry  rather-interesting  group-theory  nudge-targets  consider:exploring
february 2016 by Vaguery
[1310.8608] Lorentzian Coxeter systems and Boyd-Maxwell ball packings
In the recent study of infinite root systems, fractal patterns of ball packings were observed while visualizing roots in affine space. In this paper, we show that the observed fractals are exactly the ball packings described by Boyd and Maxwell. This correspondence is a corollary of a more fundamental result: Given a geometric representation of a Coxeter group in a Lorentz space, the set of limit directions of weights equals the set of limit roots. Additionally, we use Coxeter complexes to describe tangency graphs of the corresponding Boyd--Maxwell ball packings. Finally, we enumerate all the Coxeter systems that generate Boyd-Maxwell ball packings.
group-theory  graph-theory  fractals  packing-problems  geometry  computational-geometry  nudge-targets  consider:representation
december 2015 by Vaguery
[1312.5175] Computer-verification of the structure of some classes of fragile matroids
This technical report accompanies the following three papers. It contains the computations necessary to verify some of the results claimed in those papers.
[1] Carolyn Chun, Deborah Chun, Dillon Mayhew, and Stefan H. M. van Zwam. Fan-extensions in fragile matroids. In preparation. [2] Carolyn Chun, Dillon Mayhew, Geoff Whittle, and Stefan H. M. van Zwam. The structure of binary Fano-fragile matroids. In preparation. [3] Ben Clark, Dillon Mayhew, Geoff Whittle, and Stefan H. M. van Zwam. The structure of {U2,5, U3,5}-fragile matroids. In preparation.
matroids  group-theory  algorithms  includes-code  rather-interesting  nudge-targets
november 2015 by Vaguery
[1506.01726] Virtual knot groups and almost classical knots
We define a group-valued invariant of virtual knots and relate it to various other group-valued invariants of virtual knots. In particular, we show that it is isomorphic to both the extended group of Silver-Williams and the quandle group of Manturov and Bardakov-Bellingeri. Given an almost classical knot, we show that the group factors as a free product of the usual knot group and Z. We establish a similar formula for mod p almost classical knots, and we use these results to derive obstructions to a virtual knot K being mod p almost classical.
Virtual knots can be viewed as knots in thickened surfaces, and almost classical knots correspond to knots with homologically trivial representatives. Given an almost classical knot K, we construct a Seifert surface for K and use it to extend various classical knot invariants to the setting of almost classical knots. For instance, by considering the infinite cyclic cover of the complement of K, we show that the Alexander ideal is principal, a fact that was first proved by Nakamura, Nakanishi, Satoh, and Tomiyama using different methods. This gives a natural way to extend the Alexander polynomial to almost classical knots, and we prove that the resulting polynomial satisfies a skein relation and gives a bound on the Seifert genus of K. For mod p almost classical knots, the Alexander ideal can be shown to be principal over the ring Z[z_p], where z_p is a primitive p-th root of unity, and this allows us to define an analogue to the Alexander polynomial for these knots. We use parity to show that if K is mod p almost classical, then any minimal crossing diagram for it is mod p Alexander numberable. As an application, we tabulate almost classical knots up to 6 crossings and determine their Alexander polynomials and virtual genus.
knot-theory  group-theory  to-understand  nudge-targets  consider:looking-to-see  consider:representation
november 2015 by Vaguery
[1511.00422] Abelian logic gates
An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a "toppler", which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from N^k to N^l that is the sum of a linear function and a periodic function can be expressed in terms of floors of quotients by integers, and addition.
computer-science  rather-interesting  visualization  wow-that-got-odd-real-quick  Peter-Winkler  nudge-targets  consider:looking-to-see  group-theory  proof
november 2015 by Vaguery
[1308.3819] Fast Basins and Branched Fractal Manifolds of Attractors of Iterated Function Systems
The fast basin of an attractor of an iterated function system (IFS) is the set of points in the domain of the IFS whose orbits under the associated semigroup intersect the attractor. Fast basins can have non-integer dimension and comprise a class of deterministic fractal sets. The relationship between the basin and the fast basin of a point-fibred attractor is analyzed. To better understand the topology and geometry of fast basins, and because of analogies with analytic continuation, branched fractal manifolds are introduced. A branched fractal manifold is a metric space constructed from the extended code space of a point-fibred attractor, by identifying some addresses. Typically, a branched fractal manifold is a union of a nondenumerable collection of nonhomeomorphic objects, isometric copies of generalized fractal blowups of the attractor.
dynamical-systems  fractals  IFS  self-similarity  rather-interesting  algegraic-geometry  group-theory  nudge-targets  consider:as-preimage
november 2015 by Vaguery
[1506.08518] Fast Computation of Abelian Runs
Given a word w and a Parikh vector , an abelian run of period  in w is a maximal occurrence of a substring of w having abelian period . Our main result is an online algorithm that, given a word w of length n over an alphabet of cardinality σ and a Parikh vector , returns all the abelian runs of period  in w in time O(n) and space O(σ+p), where p is the norm of , i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm p in w in time O(np), for any given norm p. Finally, we give an O(n2)-time offline randomized algorithm for computing all the abelian runs of w. Its deterministic counterpart runs in O(n2logσ) time.
strings  group-theory  algorithms  symmetry  rather-interesting  combinatorics  enumeration  classification  nudge-targets  consider:feature-discovery
november 2015 by Vaguery
[1507.02609] Wreath product of matrices
We introduce a new matrix product, that we call the wreath product of matrices. The name is inspired by the analogous product for graphs, and the following important correspondence is proven: the wreath product of the adjacency matrices of two graphs provides the adjacency matrix of the wreath product of the graphs. This correspondence is exploited in order to study the spectral properties of the famous Lamplighter random walk: the spectrum is explicitly determined for the "Walk or switch" model on a complete graph of any size, with two lamp colors. The investigation of the spectrum of the matrix wreath product is actually developed for the more general case where the second factor is a circulant matrix. Finally, an application to the study of generalized Sylvester matrix equations is treated.
graph-theory  group-theory  rather-interesting  discrete-mathematics  exploration  mathematical-recreations  nudge-targets  consider:looking-to-see
november 2015 by Vaguery
[1411.3647] The infinite cyclohedron and its automorphism group
Cyclohedra are a well-known infinite familiy of finite-dimensional polytopes that can be constructed from centrally symmetric triangulations of even-sided polygons. In this article we introduce an infinite-dimensional analogue and prove that the group of symmetries of our construction is a semidirect product of a degree 2 central extension of Thompson's infinite finitely presented simple group T with the cyclic group of order 2. These results are inspired by a similar recent analysis by the first author of the automorphism group of an infinite-dimensional associahedron.
group-theory  symmetry  combinatorics  rather-interesting  lovely  nudge-targets  consider:find-something-I-don't-know
september 2015 by Vaguery
[1507.02472] Post-surjectivity and balancedness of cellular automata over groups
We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every preimage of one is asymptotic to a preimage of the other. The well known dual concept is pre-injectivity: a cellular automaton is pre-injective if distinct asymptotic configurations have distinct images. We prove that pre-injective, post-surjective cellular automata over surjunctive groups are reversible. In particular, post-surjectivity and reversibility are equivalent notions on amenable groups. We also prove that reversible cellular automata over arbitrary groups are balanced, that is, they preserve the uniform measure on the configuration space.
cellular-automata  group-theory  rather-interesting  system-of-professions  nudge-targets  consider:feature-discovery  consider:performance-measures
september 2015 by Vaguery
[1507.05145] Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
It is shown that the knapsack problem (introduced by Myasnikov, Nikolaev, and Ushakov) is undecidable in a direct product of sufficiently many copies of the discrete Heisenberg group (which is nilpotent of class 2). Moreover, for the discrete Heisenberg group itself, the knapsack problem is decidable. Hence, decidability of the knapsack problem is not preserved under direct products. It is also shown that for every co-context-free group, the knapsack problem is decidable. For the subset sum problem (also introduced by Myasnikov, Nikolaev, and Ushakov) we show that it belongs to the class NL (nondeterministic logspace) for every finitely generated virtually nilpotent group and that there exists a polycyclic group with an NP-complete subset sum problem.
group-theory  out-of-the-box  (get-it?)  optimization  rather-interesting  nudge-targets  operations-research
september 2015 by Vaguery
[1307.3474] Kneading determinants of infinite order linear recurrences
Infinite order linear recurrences are studied via kneading matrices and kneading determinants. The concepts of kneading matrix and kneading determinant of an infinite order linear recurrence, introduced in this work, are defined in a purely linear algebraic context. These concepts extend the classical notions of Frobenius companion matrix to infinite order linear recurrences and to the associated discriminant of finite order linear recurrences. Asymptotic Binet formulas are deduced for general classes of infinite order linear recurrences as a consequence of the analytical properties of the generating functions obtained for the solutions of these infinite order linear recurrences.
rather-interesting  group-theory  algebra  generative-models  nudge-targets  consider:rediscovery  consider:performance-measures
september 2015 by Vaguery
[1409.3503] Matroid theory for algebraic geometers
This article is a survey of matroid theory aimed at algebraic geometers. Matroids are combinatorial abstractions of linear subspaces and hyperplane arrangements. Not all matroids come from linear subspaces; those that do are said to be representable. Still, one may apply linear algebraic constructions to non-representable matroids. There are a number of different definitions of matroids, a phenomenon known as cryptomorphism. In this survey, we begin by reviewing the classical definitions of matroids, develop operations in matroid theory, summarize some results in representability, and construct polynomial invariants of matroids. Afterwards, we focus on matroid polytopes, introduced by Gelfand-Goresky-MacPherson-Serganova, which give a cryptomorphic definition of matroids. We explain certain locally closed subsets of the Grassmannian, thin Schubert cells, which are labeled by matroids, and which have applications to representability, moduli problems, and invariants of matroids following Fink-Speyer. We explain how matroids can be thought of as cohomology classes in a particular toric variety, the permutohedral variety, by means of Bergman fans, and apply this description to give an exposition of the proof of log-concavity of the characteristic polynomial of representable matroids due to the author with Huh.
review  group-theory  matrices  algebraic-geometry  wedge-product  nudge-targets
september 2015 by Vaguery
[1504.02462] A Group Theoretic Perspective on Unsupervised Deep Learning
Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning.
One factor behind the recent resurgence of the subject is a key algorithmic step called {\em pretraining}: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations.
Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.
deep-learning  generative-models  group-theory  pre-training  rather-interesting  summary
june 2015 by Vaguery
[1312.7829] Rauzy fractals with countable fundamental group
We prove that every free group of finite rank can be realized as the fundamental group of a planar Rauzy fractal associated with a 4-letter unimodular cubic Pisot substitution. This characterizes all countable fundamental groups for planar Rauzy fractals. We give an explicit construction relying on two operations on substitutions: symbolic splittings and conjugations by free group automorphisms.
group-theory  fractals  putty-pitchers  rather-interesting  to-understand
april 2015 by Vaguery
[1412.4453] Diagrams and rectangular extensions of planar semimodular lattices
In 2009, G. Gr\"atzer and E. Knapp proved that every planar semimodular lattice has a rectangular extension. We prove that, under reasonable additional conditions, this extension is unique. This theorem naturally leads to a hierarchy of special diagrams of planar semimodular lattices. Besides that these diagrams are unique in a strong sense, we explore many of their further properties. Finally, we demonstrate the power of our new diagrams in two ways. First, we prove a simplified version of our earlier Trajectory Coloring Theorem, which describes the inclusion con(p)\supseteq\con(q) for prime intervals p and q in slim rectangular lattices. Second, we prove G. Gr\"atzer's Swing Lemma for the same lattices, which describes the same inclusion more simply.
to-understand  group-theory  graph-theory  algebra  pretty-pitchers
april 2015 by Vaguery
[1409.5159] Permutation classes
This is a survey on permutation classes for the upcoming book Handbook of Enumerative Combinatorics.
combinatorics  permutations  classification  stamp-collecting  group-theory  rather-interesting  nudge-targets  consider:rediscovery
march 2015 by Vaguery
[1307.0088] Twins in words and long common subsequences in permutations
A large family of words must contain two words that are similar. We investigate several problems where the measure of similarity is the length of a common subsequence.
We construct a family of n^{1/3} permutations on n letters, such that LCS of any two of them is only cn^{1/3}, improving a construction of Beame, Blais, and Huynh-Ngoc. We relate the problem of constructing many permutations with small LCS to the twin word problem of Axenovich, Person and Puzynina. In particular, we show that every word of length n over a k-letter alphabet contains two disjoint equal subsequences of length cnk^{-2/3}.
Many problems are left open.
combinatorics  strings  permutations  group-theory  proof  horse-races  open-questions  nudge-targets
march 2015 by Vaguery
[1412.6621] Why does Deep Learning work? - A perspective from Group Theory
Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning.
One factor behind the recent resurgence of the subject is a key algorithmic step called pre-training: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations.
Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.
deep-learning  group-theory  information-theory  statistics  neural-networks  machine-learning  philosophy-of-engineering  nudge-targets  representation  approximation  modeling
march 2015 by Vaguery
[1502.03065] Subword counting and the incidence algebra
The Pascal matrix, P, is an upper diagonal matrix whose entries are the binomial coefficients. In 1993 Call and Velleman demonstrated that it satisfies the beautiful relation P=exp(H) in which H has the numbers 1, 2, 3, etc. on its superdiagonal and zeros elsewhere. We generalize this identity to the incidence algebras I(A∗) and I() of functions on words and permutations, respectively. In I(A∗) the entries of P and H count subwords; in I() they count permutation patterns. Inspired by vincular permutation patterns we define what it means for a subword to be restricted by an auxiliary index set R; this definition subsumes both factors and (scattered) subwords. We derive a theorem for words corresponding to the Reciprocity Theorem for patterns in permutations: Up to sign, the coefficients in the Mahler expansion of a function counting subwords restricted by the set R is given by a function counting subwords restricted by the complementary set Rc.
combinatorics  counting  strings  group-theory  rather-interesting
march 2015 by Vaguery
[1502.03792] Counting toroidal binary arrays, II
We derive formulas for (i) the number of toroidal n×n binary arrays, allowing rotation of rows and/or columns as well as matrix transposition, and (ii) the number of toroidal n×n binary arrays, allowing rotation and/or reflection of rows and/or columns as well as matrix transposition.
combinatorics  counting  group-theory  symmetry  nudge-targets  consider:rediscovery  consider:representation
march 2015 by Vaguery
Associahedron - Wikipedia, the free encyclopedia
In mathematics, an associahedron Kn is an (n − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of n letters and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with n + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called Stasheff polytopes after the work of Jim Stasheff, who rediscovered them in the early 1960s[1] after earlier work on them by Dov Tamari.[2]
group-theory  define-your-terms  hunh
march 2015 by Vaguery
[1407.2464] Which nestohedra are removahedra?
A removahedron is a polytope obtained by deleting inequalities from the facet description of the classical permutahedron. Relevant examples range from the associahedra to the permutahedron itself, which raises the natural question to characterize which nestohedra can be realized as removahedra. In this note, we show that the nested complex of any connected building set closed under intersection can be realized as a removahedron. We present two different complementary proofs: one based on the building trees and the nested fan, and the other based on Minkowski sums of dilated faces of the standard simplex. In general, this closure condition is sufficient but not necessary to obtain removahedra. However, we show that it is also necessary to obtain removahedra from graphical building sets, and that it is equivalent to the corresponding graph being chordful (i.e. any cycle induces a clique).
march 2015 by Vaguery
[1405.1150] On the Local Theory of Billiards in Polygons
A periodic trajectory on a polygonal billiard table is stable if it persists under any sufficiently small perturbation of the table. It is a standard result that a periodic trajectory on an n-gon gives rise in a natural way to a closed path on an n-punctured sphere, and that the trajectory is stable iff this path is null-homologous. We present a novel proof of this result in the language of covering spaces, which generalizes to characterize the stable trajectories in neighborhoods of a polygon. Using this, we classify the stable periodic trajectories near the 30-60-90 triangle, giving a new proof of a result of Schwartz that no neighborhood of the triangle can be covered by a finite union of orbit tiles. We also extend a result of Hooper and Schwartz that the isosceles Veech triangles Vn admit no periodic trajectories for n=2m,m≥2, and examine their conjecture that no neighborhood of Vn can be covered by finitely many orbit tiles.
dynamical-systems  computational-geometry  group-theory  algorithms  rather-interesting  nudge-targets  pretty-pictures
february 2015 by Vaguery
[1501.07553] Counting polygon spaces, Boolean functions and majority games
We explain why numbers occurring in the classification of polygon spaces coincide with numbers of self-dual equivalence classes of threshold functions, or of regular Boolean functions, or of decisive weighted majority games.
combinatorics  counting  group-theory  patterns  rather-odd
february 2015 by Vaguery
[1001.5471] Bulking II: Classifications of Cellular Automata
This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc) providing several formal tools allowing to classify cellular automata.
cellular-automata  Erik's-problem?  rescaling  group-theory  formal-languages  Misrepresentations
february 2015 by Vaguery
[1404.0948] The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes
Previous work identifying depth-optimal n-channel sorting networks for 9≤n≤16 is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until n=40.
sorting  optimization  group-theory  symmetry  you-keep-using-that-word  it's-counterintuitive-they-say  nudge-targets  consider:representation  consider:rule-discovery-as-such
january 2015 by Vaguery
[1412.6621v2] Why does Deep Learning work? - A perspective from Group Theory
Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning.
One factor behind the recent resurgence of the subject is a key algorithmic step called pre-training: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations.
Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.
machine-learning  deep-learning  group-theory  rather-interesting  explanation
january 2015 by Vaguery
[1410.0417] Visualising the arithmetic of quadratic imaginary fields
We study the orbit of ℝ under the Bianchi group PSL2(K), where K is an imaginary quadratic field. The orbit, called a Schmidt arrangement K, is a geometric realisation, as an intricate circle packing, of the arithmetic of K. This paper presents several examples of this phenomenon. First, we show that the curvatures of the circles are integer multiples of −Δ‾‾‾‾√ and describe the curvatures of tangent circles in terms of the norm form of K. Second, we show that the circles themselves are in bijection with certain ideal classes in orders of K, the conductor being a certain multiple of the curvature. This allows us to count circles with class numbers. Third, we show that the arrangement of circles is connected if and only if K is Euclidean. These results are meant as foundational for a study of a new class of thin groups generalising Apollonian groups, in a companion paper.
group-theory  visualization  pretty  computational-geometry
january 2015 by Vaguery
[1212.5951] Cellular automata between sofic tree shifts
We study the sofic tree shifts of AΣ∗, where Σ∗ is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if X⊂AΣ∗ is a sofic tree shift, then the configurations in X whose orbit under the shift action is finite are dense in X, and, as a consequence of this, we deduce that every injective cellular automata τ:X→X is surjective. Moreover, a characterization of sofic tree shifts in terms of general Rabin automata is given.
We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.
cellular-automata  group-theory  out-of-the-box  rather-interesting  wish-I-could-follow-it-better  discrete-mathematics
january 2015 by Vaguery
[1402.3881] New Results on Doubly Adjacent Pattern-Replacement Equivalences
In this paper, we consider the family of pattern-replacement equivalence relations referred to as the "indices and values adjacent" case. Each such equivalence is determined by a partition P of a subset of Sc for some c. In 2010, Linton, Propp, Roby, and West posed a number of open problems in the area of pattern-replacement equivalences. Five, in particular, have remained unsolved until now, the enumeration of equivalence classes under the {123,132}-equivalence, under the {123,321}-equivalence, under the {123,132,213} equivalence, and under the {123,132,213,321}-equivalence. We find formulas for three of the five equivalences and systems of representatives for the equivalence classes of the other two. We generalize our results to hold for all replacement partitions of S3, as well as for an infinite family of other replacement partitions. In addition, we characterize the equivalence classes in Sn under the Sc-equivalence, finding a generalization of Stanley's results on the {12,21}-equivalence.
To do this, we introduce a notion of confluence that often allows one to find a representative element in each equivalence class under a given equivalence relation. Using an inclusion-exclusion argument, we are able to use this to count the equivalence classes under equivalence relations satisfying certain conditions.
combinatorics  group-theory  strings  algorithms  nudge-targets  consider:recognizers  consider:extended-regexes
march 2014 by Vaguery
[1204.3216] Towards A Categorical Approach of Transformational Music Theory
Transformational music theory mainly deals with group and group actions on sets, which are usually constituted by chords. For example, neo-Riemannian theory uses the dihedral group D24 to study transformations between major and minor triads, the building blocks of classical and romantic harmony. Since the developments of neo-Riemannian theory, many developments and generalizations have been proposed, based on other sets of chords, other groups, etc. However music theory also face problems for example when defining transformations between chords of different cardinalities, or for transformations that are not necessarily invertible. This paper introduces a categorical construction of musical transformations based on category extensions using groupoids. This can be seen as a generalization of a previous work which aimed at building generalized neo-Riemannian groups of transformations based on group extensions. The categorical extension construction allows the definition of partial transformations between different set-classes. Moreover, it can be shown that the typical wreath products groups of transformations can be recovered from the category extensions by "packaging" operators and considering their composition.
group-theory  esoterica  music  composition  models-and-modes  rather-odd  interesting
march 2014 by Vaguery
[1309.3060] On SAT representations of XOR constraints
We study the representation of systems S of linear equations over the two-element field via conjunctive normal forms F (boolean clause-sets). First we study the problem of finding an arc-consistent representation ("AC"). Our main negative result is that there is no polysize AC representation in general. On the positive side we show that finding such an AC representation is fixed-parameter tractable (fpt) in the number of equations. Then we turn to a stronger criterion of representation, namely propagation completeness ("PC") --- while AC only covers the variables of S, now all the variables in F (the variables in S plus auxiliary variables) are considered for PC. We show that the standard translation actually yields a PC representation for one equation, but fails so for two equations (in fact arbitrarily badly). We show that with a more intelligent translation we can also easily compute a translation to PC for two equations. We conjecture that computing a representation in PC is fpt in the number of equations.
satisfiability  group-theory  representation  performance-measure  nudge-targets
september 2013 by Vaguery
[1211.5389] Algorithms for Computing Abelian Periods of Words
Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.
strings  group-theory  algorithms  combinatorics  something-about-generating-processes  nudge-targets
june 2013 by Vaguery
[1306.0019] Recursive Sorting in Lattices
The direct application of the definition of sorting in lattices is impractical because it leads to an algorithm with exponential complexity. In this paper we present for distributive lattices a recursive formulation to compute the sort of a sequence. This alternative formulation is inspired by the identity that underlies Pascal's triangle. It provides quadratic complexity and is in fact a generalization of insertion sort for lattices.
group-theory  I-think  sorting  multiobjective-optimization  algorithms  nudge-targets  alternate-ontologies
june 2013 by Vaguery
[1305.0448] A Fast Search Algorithm for &lt;m,m,m&gt; Triple Product Property Triples and an Application for 5x5 Matrix Multiplication
We present a new fast search algorithm for <m,m,m> Triple Product Property (TPP) triples as defined by Cohn and Umans in 2003. The new algorithm achieves a speed-up factor of 40 up to 194 in comparison to the best known search algorithm. With a parallelized version of the new algorithm we are able to search for TPP triples in groups up to order 55.
As an application we identify a list of groups that would realize 5x5 matrix multiplication with under 100 resp. 125 scalar multiplications (the best known upper bound by Makarov 1987 resp. the trivial upper bound) if they contain a <5,5,5> TPP triple. With our new algorithm we show that no group can realize 5x5 matrix multiplication better than Makarov's algorithm.
matrices  group-theory  algorithms  computational-complexity  nudge-targets
may 2013 by Vaguery
[1211.5466] Examples of substitution systems and their factors
The theory of substitution sequences and their higher-dimensional analogues is intimately connected with symbolic dynamics. By systematically studying the factors (in the sense of dynamical systems theory) of a substitution dynamical system, one can reach a better understanding of spectral and topological properties. We illustrate this point of view by means of some characteristic examples, including a rather universal substitution in one dimension as well as the squiral and the table tilings of the plane.
rewriting  grammar  engineering-design  dynamical-systems  computer-science  group-theory  nudge-targets  formalization
april 2013 by Vaguery
[1212.6648] Partition regularity in the rationals
A system of homogeneous linear equations with integer coefficients is partition regular if, whenever the natural numbers are finitely coloured, the system has a monochromatic solution. The Finite Sums theorem provided the first example of an infinite partition regular system of equations. Since then, other such systems of equations have been found, but each can be viewed as a modification of the Finite Sums theorem.

We present here a new infinite partition regular system of equations that appears to arise in a genuinely different way. This is the first example of a partition regular system in which a variable occurs with unbounded coefficients. A modification of the system provides an example of a system which is partition regular over Q but not N, settling another open problem.
combinatorics  group-theory  graph-theory  number-theory  nudge-targets
march 2013 by Vaguery
[1007.2460] Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry
"We describe computer algorithms that produce the complete set of isohedral tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains and the tilings have 3-, 4-, or 6-fold rotational symmetry. The symmetry groups of such tilings are of types p3, p31m, p4, p4g, and p6. There are no isohedral tilings with symmetry groups p3m1, p4m, or p6m that have polyominoes or polyiamonds as fundamental domains. We display the algorithms' output and give enumeration tables for small values of n.…"
computational-geometry  algorithms  mathematical-recreations  group-theory  symmetry  nudge-targets  tiling
july 2010 by Vaguery
[1007.0221] Regular Labelings and Geometric Structures
"We have described three types of geometric object that have natural encodings as regular labelings of a maximal or near-maximal planar graph. Although much about these labelings is known, there are still many questions remaining:…"
nudge-targets  geometry  computational-geometry  visualization  algorithms  group-theory
july 2010 by Vaguery