Frobenius problem and dead ends in integers

DOI10.1016/J.JNT.2007.03.015MaRDI QIDQ2483162zbMATH OpenOpenAlexFDO

Authors Zoran Šunić

Publication date 28 April 2008

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0612271

zbMATH Keywords

Cayley graphdead endsFrobenius problemintegers

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Linear Diophantine equations (11D04) Geometric group theory (20F65)

Abstract: Let a and b be positive, relatively prime integers. We show that the following are equivalent: (i) d is a dead end in the (symmetric) Cayley graph of Z with respect to a and b, (ii) d is a Frobenius value with respect to a and b (it cannot be written as a non-negative or non-positive integer linear combination of a and b), and d is maximal (in the Cayley graph) with respect to this property. In addition, for given integers a and b, we explicitly describe all such elements in Z. Finally, we show that Z has only finitely many dead ends with respect to any finite symmetric generating set. In the appendix we show that every finitely generated group has a generating set with respect to which dead ends exist.

Review text

Let \(G\) be a group generated by a finite set \(S\). The word length of an element \(g\) with respect to \(S\), denoted by \(l(g)\), is the shortest length of a group word over \(S\) representing \(g\). The Cayley graph of \(G\) with respect to \(S\) is the graph whose vertices are the elements of \(G\) and in which two vertices \(g\) and \(h\) are connected by an edge if and only if \(g= hs\) for some \(s\) in \(S\cup S^{-1}\). A dead end in \(G\) with respect to \(S\) is an element \(d\) in \(G\) such that \(l(ds)\leq l(d)\) for every \(s\) in \(S\cup S^{-1}\). In this paper, the author gives a connection of dead ends in Cayley graphs with the Diophantine Frobenius problem. The author also describes all dead ends when \(G= \mathbb Z\) in the case when \(S\) consists of two elements. In an appendix, the author shows that every finitely generated group has a generating set with respect to which dead ends exist.

Recommendations

• Strict Dead-End Elements in Free Soluble Groups
• A finitely presented group with unbounded dead-end depth
• Dead end words in lamplighter groups and other wreath products
• SOME REMARKS ON DEPTH OF DEAD ENDS IN GROUPS
• THE UNBOUNDED DEAD-END DEPTH PROPERTY IS NOT A GROUP INVARIANT

Cites work

• A finitely presented group with unbounded dead-end depth
• Combinatorial properties of Thompson’s group 𝐹
• Dead end words in lamplighter groups and other wreath products
• Deep pockets in lattices and other groups.
• Frobenius problem and the covering radius of a lattice
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Infinite commensurable hyperbolic groups are bi-Lipschitz equivalent
• Lattice translates of a polytope and the Frobenius problem
• On amenability of group algebras. I.
• Representations of integers by linear forms in nonnegative integers
• Solution of the Burnside problem for exponent six
• Strict Dead-End Elements in Free Soluble Groups
• The Frobenius problem, rational polytopes, and Fourier-Dedekind sums
• THE UNBOUNDED DEAD-END DEPTH PROPERTY IS NOT A GROUP INVARIANT

Cited in

(4)

• Modular hyperbolas
• Iterated Minkowski sums, horoballs and north-south dynamics
• Strict Dead-End Elements in Free Soluble Groups
• Dead ends on wreath products and lamplighter groups

This page was built for publication: Frobenius problem and dead ends in integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483162)