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

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

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.G. Castelli, F. Mignosi, A. Restivo,*Fine and Wilf's theorem for three periods and a generalization of Sturmian words*, Theor. Comput. Sci.**218**(1999), 83-94. MR**2000c:68110****3.**N.J. Fine, H.S. Wilf,*Uniqueness theorem for periodic functions*, Proc. Amer. Math. Soc.**16**(1965), 109-114. MR**30:5124****4.**R. Giancarlo, F. Mignosi,*Generalizations of the periodicity theorem of Fine and Wilf*, CAAP '94, LNCS**787**(1994), 130-141. MR**95g:68091****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.**Sh. Ito, M. Kimura,*On Rauzy fractal*, Japan J. Indust. Appl. Math.**8**(1991), 461-486. MR**93d:11084****7.**J. Justin,*On a paper by Castelli, Mignosi, Restivo*, RAIRO: Theoret. Informatics Appl.**34**(2000), 373-377. MR**2002d:68089****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.**M. Regnier, L. Rostami,*A unifying look at**-dimensional periodicities and space coverings*, Proc. 4th Symp. on Combinatorial Pattern Matching LNCS**684**(1993), 215-227. MR**94j:68310****11.**Ö. Rödseth,*On a linear diophantine problem of Frobenius*, J. reine angew. Math.**301**(1978), 171-178. MR**58:27741****12.**E.S. Selmer,*On the linear diophantine problem of Frobenius*, J. reine angew. Math.**293/294**(1977), 1-17. MR**56:246****13.**E.S. Selmer, Ö. Beyer,*On the linear diophantine problem of Frobenius in three variables*, J. reine angew. Math.**301**(1978), 161-170. MR**58:27740****14.**C. Smorynski,*Skolem's solution to a problem of Frobenius*, Math. Intelligencer**3**(1981), 123-132. MR**83b:03031****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:
https://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