Multidimensional 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), 16611671
MSC (2000):
Primary 05D99, 06B25, 11Axx, 11B75, 68R15
Published electronically:
January 15, 2003
MathSciNet review:
1953570
Fulltext 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 nontrivial linear combination of with nonnegative 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' Coinchanging Problem in the case of coins of two denominations.
 1.
A. Amir, G.E. Benson, Alphabet independent twodimensional pattern matching, Proc. 24th ACM Symp. Theory on Comp. (1992) pp. 5968.
 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 (2000c:68110), http://dx.doi.org/10.1016/S03043975(98)002515
 3.
N.
J. Fine and H.
S. Wilf, Uniqueness theorems for periodic
functions, Proc. Amer. Math. Soc. 16 (1965), 109–114. MR 0174934
(30 #5124), http://dx.doi.org/10.1090/S00029939196501749349
 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
(95g:68091), http://dx.doi.org/10.1007/BFb0017478
 5.
Z. Galil, K. Park, Truly alphabet independent twodimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992), 247256.
 6.
Shunji
Ito and Minako
Kimura, On Rauzy fractal, Japan J. Indust. Appl. Math.
8 (1991), no. 3, 461–486. MR 1137652
(93d:11084), http://dx.doi.org/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
(2002d:68089), http://dx.doi.org/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
(94j:68310), http://dx.doi.org/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
(58 #27741)
 12.
Ernst
S. Selmer, On the linear Diophantine problem of Frobenius, J.
Reine Angew. Math. 293/294 (1977), 1–17. MR 0441855
(56 #246)
 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
(58 #27740)
 14.
C.
Smoryński, Skolem’s solution to a problem of
Frobenius, Math. Intelligencer 3 (1980/81),
no. 3, 123–132. MR 642131
(83b:03031), http://dx.doi.org/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.
 1.
 A. Amir, G.E. Benson, Alphabet independent twodimensional pattern matching, Proc. 24th ACM Symp. Theory on Comp. (1992) pp. 5968.
 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), 8394. MR 2000c:68110
 3.
 N.J. Fine, H.S. Wilf, Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc. 16 (1965), 109114. MR 30:5124
 4.
 R. Giancarlo, F. Mignosi, Generalizations of the periodicity theorem of Fine and Wilf, CAAP '94, LNCS 787 (1994), 130141. MR 95g:68091
 5.
 Z. Galil, K. Park, Truly alphabet independent twodimensional pattern matching, Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992), 247256.
 6.
 Sh. Ito, M. Kimura, On Rauzy fractal, Japan J. Indust. Appl. Math. 8 (1991), 461486. MR 93d:11084
 7.
 J. Justin, On a paper by Castelli, Mignosi, Restivo, RAIRO: Theoret. Informatics Appl. 34 (2000), 373377. 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), 215227. MR 94j:68310
 11.
 Ö. Rödseth, On a linear diophantine problem of Frobenius, J. reine angew. Math. 301 (1978), 171178. MR 58:27741
 12.
 E.S. Selmer, On the linear diophantine problem of Frobenius, J. reine angew. Math. 293/294 (1977), 117. MR 56:246
 13.
 E.S. Selmer, Ö. Beyer, On the linear diophantine problem of Frobenius in three variables, J. reine angew. Math. 301 (1978), 161170. MR 58:27740
 14.
 C. Smorynski, Skolem's solution to a problem of Frobenius, Math. Intelligencer 3 (1981), 123132. 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.
Similar Articles
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/S0002993903069703
PII:
S 00029939(03)069703
Keywords:
Periodicity,
Frobenius,
lattice,
coinchanging
Received by editor(s):
December 31, 2001
Published electronically:
January 15, 2003
Communicated by:
David E. Rohrlich
Article copyright:
© Copyright 2003
American Mathematical Society
