Balance properties of multi-dimensional words. (English) Zbl 0997.68091

Berthé, Valérie; Tijdeman, Robert

Theor. Comput. Sci. 273, No. 1-2, 197-224 (2002).

Summary: A word \(u\) is called 1-balanced if for any two factors \(v\) and \(w\) of \(u\) of equal length, we have \(-1<|v|_{i}-|w|_{i}<1\) for each letter \(i,\) where \(|v|_{i}\) denotes the number of occurrences of \(i\) in the factor \(v.\) The aim of this paper is to extend the notion of balance to multi-dimensional words. We first characterize all 1-balanced words on \(Z^{n}.\) In particular, we prove they are fully periodic for \(n>1.\) We then give a quantitative measure of non-balancedness for some words on \(Z^{2}\) with irrational density, including two-dimensional Sturmian words.

MSC:

68R15

Combinatorics on words

Keywords:

1-balanced words; Sturmian words

References:

[2]	Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[3]	Berthé, V.; Vuillon, L., Tilings and rotations on the torusa two-dimensional generalization of Sturmian sequences, Discrete Math., 223, 27-53 (2000) · Zbl 0970.68124
[4]	Berthé, V.; Vuillon, L., Suites doubles de basse complexité, J. Théor. Nombres Bordeaux, 12, 179-208 (2000) · Zbl 1018.37010
[5]	Brown, T. C.; Shiue, P. J.-S., Sums of fractional parts of integer multiples of an irrational, J. Number Theory, 50, 181-192 (1995) · Zbl 0824.11041
[6]	Cassaigne, J.; Ferenczi, S.; Zamboni, L. Q., Imbalances in Arnoux-Rauzy sequences, Ann. Inst. Fourier, 50, 1265-1276 (2000) · Zbl 1004.37008
[7]	Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., 255, 539-553 (2001) · Zbl 0981.68126
[8]	Dulucq, S.; Gouyou-beauchamp, D., Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[10]	Ferenczi, S., Bounded remainder sets, Acta Arith., 61, 319-326 (1992) · Zbl 0774.11037
[11]	Graham, R. L., Covering the positive integers by disjoint sets of the form \({[n α +β] : n=1,2,…}\), J. Combin. Theory A, 15, 354-358 (1973) · Zbl 0279.10042
[12]	Hardy, G. H.; Littlewood, J. E., Some problems of Diophantine approximations: the lattice-points of a right-angled triangle, Proc. London Math. Soc., 20, 15-36 (1922) · JFM 48.0197.07
[15]	Hubert, P., Well balanced sequences, Theoret. Comput. Sci., 242, 91-108 (2000) · Zbl 0944.68149
[16]	Kesten, H., On a conjecture of Erdős and Szűsz related to uniform distribution mod1, Acta Arith., 12, 193-212 (1966) · Zbl 0144.28902
[17]	Lerch, M., Question 1547, Intermédiaire Math., 11, 145-146 (1904)
[18]	Lipatov, E. P., A classification of binary collections and properties of homogeneity classes, Problemy Kibernet., 39, 67-84 (1982), (in Russian) · Zbl 0555.94007
[20]	Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci., 82, 71-84 (1991) · Zbl 0728.68093
[21]	Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[22]	Morse, M.; Hedlund, G. A., Symbolic dynamics IISturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[24]	Pinner, C., On sums of fractional parts \({n α + γ}\), J. Number Theory, 65, 48-73 (1997) · Zbl 0886.11045
[26]	Sierpinski, W., Pewne twierdzenie tyczace sie liczb niewymiernych. Un théorème sur les nombres irrationnels, Bull. Internat. Acad. Polon. Sci. Lett. Cl. Sci. Math. Naturelles Sér. A (Cracovie), 725-727 (1909)
[27]	Tijdeman, R., On complementary triples of Sturmian bisequences, Indag. Math. N. S., 7, 419-424 (1996) · Zbl 0862.68085
[29]	Tijdeman, R., Fraenkel’s conjecture for six sequences, Discrete Math., 222, 223-234 (2000) · Zbl 1101.11314
[30]	Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionnelle, Theoret. Comput. Sci., 209, 261-285 (1998) · Zbl 0913.68206
[31]	Zorich, A., Deviation for interval exchange transformations, Ergodic Theory Dynamical Systems, 17, 1477-1499 (1997) · Zbl 0958.37002