Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester

Authors:
R. J. Simpson and R. Tijdeman

Journal:
Proc. Amer. Math. Soc. **131** (2003), 1661-1671

MSC (2000):
Primary 05D99, 06B25, 11Axx, 11B75, 68R15

Published electronically:
January 15, 2003

MathSciNet review:
1953570

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be vectors in which generate . We show that a body with the vectors as edge vectors is an almost minimal set with the property that every function with periods is constant. For the result reduces to the theorem of Fine and Wilf, which is a refinement of the famous Periodicity Lemma.

Suppose is not a non-trivial linear combination of with non-negative coefficients. Then we describe the sector such that every interior integer point of the sector is a linear combination of over , but infinitely many points on each of its hyperfaces are not. For the result reduces to a formula of Sylvester corresponding to Frobenius' Coin-changing Problem in the case of coins of two denominations.

**1.**A. Amir, G.E. Benson,*Alphabet independent two-dimensional pattern matching*, Proc. 24th ACM Symp. Theory on Comp. (1992) pp. 59-68.**2.**M. Gabriella Castelli, Filippo Mignosi, and Antonio Restivo,*Fine and Wilf’s theorem for three periods and a generalization of Sturmian words*, Theoret. Comput. Sci.**218**(1999), no. 1, 83–94. WORDS (Rouen, 1997). MR**1687764**, 10.1016/S0304-3975(98)00251-5**3.**N. J. Fine and H. S. Wilf,*Uniqueness theorems for periodic functions*, Proc. Amer. Math. Soc.**16**(1965), 109–114. MR**0174934**, 10.1090/S0002-9939-1965-0174934-9**4.**R. Giancarlo and F. Mignosi,*Generalizations of the periodicity theorem of Fine and Wilf*, Trees in algebra and programming—CAAP ’94 (Edinburgh, 1994) Lecture Notes in Comput. Sci., vol. 787, Springer, Berlin, 1994, pp. 130–141. MR**1286756**, 10.1007/BFb0017478**5.**Z. Galil, K. Park,*Truly alphabet independent two-dimensional pattern matching*, Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992), 247-256.**6.**Shunji Ito and Minako Kimura,*On Rauzy fractal*, Japan J. Indust. Appl. Math.**8**(1991), no. 3, 461–486. MR**1137652**, 10.1007/BF03167147**7.**Jacques Justin,*On a paper by M. Castelli, F. Mignosi, A. Restivo. Comment on: “Fine and Wilf’s theorem for three periods and a generalization of Sturmian words” [Theoret. Comput. Sci. 218 (1999), no. 1, 83–94; MR1687764 (2000c:68110)]*, Theor. Inform. Appl.**34**(2000), no. 5, 373–377 (English, with English and French summaries). MR**1829233**, 10.1051/ita:2000122**8.**F. Mignosi, A. Restivo, P.V. Silva,*On Fine and Wilf's theorem for bidimensional words*, to appear in Theor. Computer Sc.**9.**H. Ray, R.J. Simpson,*The Frobenius problem in two dimensions*, in preparation.**10.**Mireille Régnier and Ladan Rostami,*A unifying look at 𝑑-dimensional periodicities and space coverings*, Combinatorial pattern matching (Padova, 1993) Lecture Notes in Comput. Sci., vol. 684, Springer, Berlin, 1993, pp. 215–227. MR**1253337**, 10.1007/BFb0029807**11.**Öystein J. Rödseth,*On a linear Diophantine problem of Frobenius*, J. Reine Angew. Math.**301**(1978), 171–178. MR**0557016****12.**Ernst S. Selmer,*On the linear Diophantine problem of Frobenius*, J. Reine Angew. Math.**293/294**(1977), 1–17. MR**0441855****13.**Ernst S. Selmer and Öyvind Beyer,*On the linear Diophantine problem of Frobenius in three variables*, J. Reine Angew. Math.**301**(1978), 161–170. MR**0557015****14.**C. Smoryński,*Skolem’s solution to a problem of Frobenius*, Math. Intelligencer**3**(1980/81), no. 3, 123–132. MR**642131**, 10.1007/BF03022866**15.**J.J. Sylvester,*Mathematical questions, with their solutions, Educational Times***41**(1884), 21.**16.**R. Tijdeman and L. Zamboni,*The Fine and Wilf theorem for any number of periods*, in preparation.

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
05D99,
06B25,
11Axx,
11B75,
68R15

Retrieve articles in all journals with MSC (2000): 05D99, 06B25, 11Axx, 11B75, 68R15

Additional Information

**R. J. Simpson**

Affiliation:
Department of Mathematics and Statistics, Curtin University of Technology, P.O. Box U1987, Perth, Western Australia 6001, Australia

Email:
simpson@maths.curtin.edu.au

**R. Tijdeman**

Affiliation:
Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands

Email:
tijdeman@math.leidenuniv.nl

DOI:
http://dx.doi.org/10.1090/S0002-9939-03-06970-3

Keywords:
Periodicity,
Frobenius,
lattice,
coin-changing

Received by editor(s):
December 31, 2001

Published electronically:
January 15, 2003

Communicated by:
David E. Rohrlich

Article copyright:
© Copyright 2003
American Mathematical Society