Balanced word - Revision history

VectorGraphics at 18:48, 3 May 2025

2025-05-03T18:48:49Z

← Older revision		Revision as of 18:48, 3 May 2025
Line 1:		Line 1:
	{{distinguish\|perfect balance}}		{{distinguish\|perfect balance}}{{Todo\|rework\|inline=1\|text=this can probably be explained without invoking "words"}}

	An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. The simplest non-trivial examples of balanced scales are [[MOS scales]], and balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.		An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. The simplest non-trivial examples of balanced scales are [[MOS scales]], and balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
	== Mathematical definition ==		== Mathematical definition ==

Inthar: /* Generalizations */

2024-09-04T12:31:05Z

Generalizations

← Older revision		Revision as of 12:31, 4 September 2024
Line 21:		Line 21:
	== Generalizations ==		== Generalizations ==
	# If <math> \mathsf{block\_balance}(s) \leq m,</math> then we say that ''s'' is ''m''-'''block-balanced'''{{idiosyncratic}}.		# If <math> \mathsf{block\_balance}(s) \leq m,</math> then we say that ''s'' is ''m''-'''block-balanced'''{{idiosyncratic}}.
	# The following stronger property implies ''m''-block-balancedness for ''m'' ≥ 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(<i>w'</i>) = len(''w'') + ''m'' + 1 satisfies \|<i>w'</i>\|<sub>''a''</sub> ~~≥~~ \|''w''\|<sub>''a''</sub> ~~+ 1~~.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales\|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)		# The following stronger property implies ''m''-block-balancedness for ''m'' ≥ 1 but is not equivalent to it unless ''m'' = 1: ''s'' is ''m''-'''chain-balanced'''{{idiosyncratic}} if for every letter ''a'' in ''s'' and every factor of ''s'' of the form ''awa'', any factor ''w' '' in ''s'' such that len(<i>w'</i>) = len(''w'') + ''m'' + 1 satisfies \|<i>w'</i>\|<sub>''a''</sub> > \|''w''\|<sub>''a''</sub>.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> (Compare [[recursive structure of MOS scales\|MOS chunks]]; proving that the chunk sizes in a MOS themselves form a MOS word proves that for binary scales, balanced implies 1-chain-balanced.)

	Block and chain balancedness are equivalent for balanced scales (which are 1-balanced in both senses) and ternary billiard ones, but ''m''-chain-balancedness is stronger than ''m''-block-balancedness in the general case.		Block and chain balancedness are equivalent for balanced scales (which are 1-balanced in both senses) and ternary billiard ones, but ''m''-chain-balancedness is stronger than ''m''-block-balancedness in the general case.

Inthar: /* Mathematical definition */

2024-09-04T11:56:28Z

Mathematical definition

← Older revision		Revision as of 11:56, 4 September 2024
Line 10:		Line 10:
	Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:		Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:

	<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1,</math>		<math> \mathsf{block\_balance}(s) := \max \big\{ \mathsf{block\_balance}(s, a) : a \text{ is a letter of }s \big\} \leq 1.</math>

	== Properties ==		== Properties ==

Lhearne: /* Properties */ added link to Fraenkel word page

2024-02-19T03:43:53Z

Properties: added link to Fraenkel word page

← Older revision		Revision as of 03:43, 19 February 2024
Line 15:		Line 15:
	* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words, and ternary balanced periodic words have maximum variety 3.		* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words, and ternary balanced periodic words have maximum variety 3.
	* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>		* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>
	* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.		* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the [[Fraenkel word]] ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.
	** A ''congruence word'' is a word ''u'' where the set of occurrences of each letter ''m'' in ''u'' is an arithmetic progression <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers ''a''<sub>''m''</sub> and ''b''<sub>''m''</sub>, ''a''<sub>''m''</sub> ≠ 0.		** A ''congruence word'' is a word ''u'' where the set of occurrences of each letter ''m'' in ''u'' is an arithmetic progression <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers ''a''<sub>''m''</sub> and ''b''<sub>''m''</sub>, ''a''<sub>''m''</sub> ≠ 0.
	** A ''congruence substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'', where ''u'' is a congruence word over a set of letters disjoint from that of ''w'', for all positive integers ''k''.		** A ''congruence substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'', where ''u'' is a congruence word over a set of letters disjoint from that of ''w'', for all positive integers ''k''.

Inthar: /* Properties */

2024-02-02T19:37:44Z

Properties

← Older revision		Revision as of 19:37, 2 February 2024
Line 13:		Line 13:

	== Properties ==		== Properties ==
	* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words.		* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words, and ternary balanced periodic words have maximum variety 3.
	* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>		* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>
	* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.		* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.

Inthar at 18:01, 21 January 2024

2024-01-21T18:01:42Z

← Older revision		Revision as of 18:01, 21 January 2024
Line 1:		Line 1:
	{{distinguish\|perfect balance}}		{{distinguish\|perfect balance}}
	An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. ~~Balanced~~ words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.		An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. The simplest non-trivial examples of balanced scales are [[MOS scales]], and balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
	== Mathematical definition ==		== Mathematical definition ==
	Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define		Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

Inthar at 18:00, 21 January 2024

2024-01-21T18:00:38Z

← Older revision		Revision as of 18:00, 21 January 2024
Line 1:		Line 1:
	{{distinguish\|perfect balance}}		{{distinguish\|perfect balance}}
	An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.		An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
	== Mathematical definition ==		== Mathematical definition ==
	Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define		Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

Inthar at 17:58, 21 January 2024

2024-01-21T17:58:09Z

← Older revision		Revision as of 17:58, 21 January 2024
Line 1:		Line 1:
	{{distinguish\|perfect balance}}		{{distinguish\|perfect balance}}
	An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the ~~balancedness~~, for any step size, ~~the property stipulates that~~ no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.		An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the property, it stipulates that for any step size, no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
	== Mathematical definition ==		== Mathematical definition ==
	Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define		Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

Inthar: /* Mathematical definition */

2024-01-21T17:56:10Z

Mathematical definition

← Older revision		Revision as of 17:56, 21 January 2024
Line 4:		Line 4:
	Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define		Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

	<math> \mathsf{block\_balance}(s, a) := \max \big\{ \big\| \|w\|_{a} - \|w'\|_{a} \big\| : w, w'~~\text{ are length-}k \text{ subwords of } s~~\big\},</math>		<math> \mathsf{block\_balance}(s, a) := \max \big\{ \big\| \|w\|_{a} - \|w'\|_{a} \big\| : \|w\| = \|w'\| \big\},</math>

	where \|''u''\|<sub>''a''</sub> is the number of occurrences of the letter ''a'' in the word ''u''.		where \|''u''\|<sub>''a''</sub> is the number of occurrences of the letter ''a'' in the word ''u'' and \|''u''\| is the length of the word ''u''.

	Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:		Then ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following:

Inthar at 17:54, 21 January 2024

2024-01-21T17:54:45Z

← Older revision		Revision as of 17:54, 21 January 2024
Line 1:		Line 1:
	{{distinguish\|perfect balance}}		{{distinguish\|perfect balance}}
	An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the balancedness, for any step size, the property stipulates that no two ''k''-steps can differ too much in how many times the step size occurs in them.		An abstract scale pattern is '''balanced''' if it satisfies a certain (quite strong) restriction on how much the intervals in within any of the scale's interval classes can differ; by one characterization of the balancedness, for any step size, the property stipulates that no two ''k''-steps can differ too much in how many times the step size occurs in them. Balanced words are one of many possible generalizations of [[MOS scale]]s to scales with three or more step sizes.
			== Mathematical definition ==
	~~Mathematically, let~~ ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define		Let ''a'' be a letter in a [[word]] or [[necklace]] ''s''. Define

	<math> \mathsf{block\_balance}(s, a) := \max \big\{ \big\| \|w\|_{a} - \|w'\|_{a} \big\| : w, w'\text{ are length-}k \text{ subwords of } s\big\},</math>		<math> \mathsf{block\_balance}(s, a) := \max \big\{ \big\| \|w\|_{a} - \|w'\|_{a} \big\| : w, w'\text{ are length-}k \text{ subwords of } s\big\},</math>