**Vaguery + group-theory**
62

Multiplying Non-Numbers

8 days ago by Vaguery

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:

out-of-the-box
geometry
group-theory
to-write-about
have-written-about
8 days ago by Vaguery

The Sum-Product Problem Shows How Addition and Multiplication Constrain Each Other | Quanta Magazine

april 2019 by Vaguery

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}$

december 2018 by Vaguery

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.

group-theory
combinatorics
algorithms
rather-interesting
feature-construction
to-understand
to-write-about
an-example-would-be-useful-about-now
december 2018 by Vaguery

[1808.08697] Universal groups of cellular automata

december 2018 by Vaguery

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

october 2018 by Vaguery

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

august 2018 by Vaguery

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é

february 2018 by Vaguery

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
But do they still hold more secrets? I think so!

february 2018 by Vaguery

[1709.07504] Hopf monoids and generalized permutahedra

january 2018 by Vaguery

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

december 2017 by Vaguery

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

[1701.06794] Computations with p-adic numbers

april 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

june 2016 by Vaguery

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

may 2016 by Vaguery

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

april 2016 by Vaguery

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
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.

april 2016 by Vaguery

[1507.02762] A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino

april 2016 by Vaguery

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

april 2016 by Vaguery

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

april 2016 by Vaguery

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

march 2016 by Vaguery

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

march 2016 by Vaguery

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

march 2016 by Vaguery

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

march 2016 by Vaguery

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

march 2016 by Vaguery

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

february 2016 by Vaguery

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

december 2015 by Vaguery

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

november 2015 by Vaguery

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
[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.

november 2015 by Vaguery

[1506.01726] Virtual knot groups and almost classical knots

november 2015 by Vaguery

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
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.

november 2015 by Vaguery

[1511.00422] Abelian logic gates

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

november 2015 by Vaguery

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

september 2015 by Vaguery

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

september 2015 by Vaguery

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

september 2015 by Vaguery

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

september 2015 by Vaguery

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

september 2015 by Vaguery

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

june 2015 by Vaguery

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
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.

june 2015 by Vaguery

[1312.7829] Rauzy fractals with countable fundamental group

april 2015 by Vaguery

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

april 2015 by Vaguery

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

march 2015 by Vaguery

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

march 2015 by Vaguery

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
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.

march 2015 by Vaguery

[1412.6621] Why does Deep Learning work? - A perspective from Group Theory

march 2015 by Vaguery

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
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.

march 2015 by Vaguery

[1502.03065] Subword counting and the incidence algebra

march 2015 by Vaguery

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

march 2015 by Vaguery

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

march 2015 by Vaguery

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?

march 2015 by Vaguery

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).

group-theory
combinatorics
can't-wait-to-understand-what-the-hell-they're-talking-about
rather-interesting
march 2015 by Vaguery

[1405.1150] On the Local Theory of Billiards in Polygons

february 2015 by Vaguery

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

february 2015 by Vaguery

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

february 2015 by Vaguery

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

january 2015 by Vaguery

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

january 2015 by Vaguery

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
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.

january 2015 by Vaguery

[1410.0417] Visualising the arithmetic of quadratic imaginary fields

january 2015 by Vaguery

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

january 2015 by Vaguery

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
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.

january 2015 by Vaguery

[1402.3881] New Results on Doubly Adjacent Pattern-Replacement Equivalences

march 2014 by Vaguery

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
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.

march 2014 by Vaguery

[1204.3216] Towards A Categorical Approach of Transformational Music Theory

march 2014 by Vaguery

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

september 2013 by Vaguery

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

june 2013 by Vaguery

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

june 2013 by Vaguery

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 <m,m,m> Triple Product Property Triples and an Application for 5x5 Matrix Multiplication

may 2013 by Vaguery

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
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.

may 2013 by Vaguery

[1211.5466] Examples of substitution systems and their factors

april 2013 by Vaguery

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

march 2013 by Vaguery

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
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.

march 2013 by Vaguery

[1007.2460] Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry

july 2010 by Vaguery

"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

july 2010 by Vaguery

"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

[1006.1126] Body-and-cad Geometric Constraint Systems

june 2010 by Vaguery

"Motivated by constraint-based CAD software, we develop the foundation for the rigidity theory of a very general model: the body-and-cad structure, composed of rigid bodies in 3D constrained by pairwise coincidence, angular and distance constraints. We identify 21 relevant geometric constraints and develop the corresponding infinitesimal rigidity theory for these structures. The classical body-and-bar rigidity model can be viewed as a body-and-cad structure that uses only one constraint from this new class. As a consequence, we identify a new, necessary, but not sufficient, counting condition for minimal rigidity of body-and-cad structures: nested sparsity. This is a slight generalization of the well-known sparsity condition of Maxwell."

engineering
mathematics
rigidity-theory
geometry
group-theory
formalization
models
june 2010 by Vaguery

**related tags**

Copy this bookmark: