# Van der Waerden's Theorem and Avoidability in Words

@inproceedings{Au2011VanDW, title={Van der Waerden's Theorem and Avoidability in Words}, author={Yu Hin Au and Aaron Robertson and Jeffrey Shallit}, booktitle={Integers}, year={2011} }

Abstract Independently, Pirillo and Varricchio, Halbeisen and Hungerbühler and Freedman considered the following problem, open since 1992: Does there exist an infinite word w over a finite subset of ℤ such that w contains no two consecutive blocks of the same length and sum? We consider some variations on this problem in the light of van der Waerden's theorem on arithmetic progressions.

#### 8 Citations

On Abelian and Additive Complexity in Infinite Words

- Mathematics, Computer Science
- Integers
- 2012

Bounded additive complexity for infinite words over a finite subset of . Expand

Sequences on Sets of Four Numbers

- Mathematics, Computer Science
- Integers
- 2016

The answer is “no” for all 4-element sets of real numbers and g(T) is found to be the maximum length of a word over T which does not contain any two consecutive blocks with the same length and the same sum. Expand

On Additive Complexity of Infinite Words

- Mathematics
- 2012

We consider questions related to the structure of infinite words (over an integer alphabet) with bounded additive complexity, i.e., words with the property that the number of distinct sums exhibited… Expand

Mathematisches Forschungsinstitut Oberwolfach Mini-workshop: Combinatorics on Words

- 2010

The area of combinatorics on words is concerned with properties of sequences of symbols. It is characteristic to the field that questions arise from various mathematical problems, and hence, many… Expand

Avoiding Three Consecutive Blocks of the Same Size and Same Sum

- Computer Science, Mathematics
- J. ACM
- 2014

We show that there exists an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and… Expand

On Double 3-Term Arithmetic Progressions

- Mathematics, Computer Science
- Integers
- 2014

This note considers a few variations of the problem, discusses some related properties of double arithmetic progressions, and presents several results obtained by using RamseyScript, a high-level scripting language. Expand

Deciding Properties of Automatic Sequences

- Mathematics
- 2013

In this thesis, we show that several natural questions about automatic sequences can be expressed as logical predicates and then decided mechanically. We extend known results in this area to broader… Expand

Approximations of Additive Squares in Infinite Words

- Mathematics, Computer Science
- Integers
- 2012

Abstract. We show that every infinite word on a finite subset of must contain arbitrarily large factors which are “close” to being additive squares. We also show that for all , must contain a factor… Expand

#### References

SHOWING 1-10 OF 27 REFERENCES

AN APPLICATION OF VAN DER WAERDEN'S THEOREM IN ADDITIVE NUMBER THEORY

- Mathematics
- 2000

A sequence on a finite set of symbols is called strongly non-repetitive if no two adjacent (finite) segments are permutations of each other. Replacing the finite set of symbols of a strongly… Expand

ON THE GROWTH OF A VAN DER WAERDEN-LIKE FUNCTION

- Mathematics
- 2006

Let W(3,k) denote the largest integer w such that there is a red/blue coloring of {1,2,... ,w} which has no red 3-term arithmetic progression and no block of k consecutive blue integers. We show that… Expand

Roth’s theorem on progressions revisited

- Mathematics
- 2008

This paper is a sequel to [B]. Our main result is an improvement of the density condition for a subset A ⊂ {1,. .. , N } to contain a nontrivial arithmetic progression of length 3. More specifically,… Expand

Abelian Squares are Avoidable on 4 Letters

- Mathematics, Computer Science
- ICALP
- 1992

It is proved that the morphism g itself is a-2-free, that is, g(w) is an a- 2-free word w in Σ*. Expand

Avoiding Abelian Powers in Binary Words with Bounded Abelian Complexity

- Mathematics, Computer Science
- Int. J. Found. Comput. Sci.
- 2011

The existence of uniformly recurrent binary words, having bounded Abelian complexity, which admit an infinite number of suffixes which do not begin in an Abelian square is shown. Expand

Some unsolved problems.

- Mathematics
- 1957

Assumption University of Windsor sponsored a symposium for mathematicians from Ontario, Michigan, and Indiana, The symposium gave occasion for an informal lecture in which I discussed various old and… Expand

Some unsolved problems.

- Medicine
- Hospital management
- 1952

where tn is a hypergeometric term, that is, tn+1/tn is a rational function of n. Our question roughly is this how fast can such a series converge to π? Of course without further conditions the… Expand

Généralisation du Théorème de van der Waerden sur les Semi-groupes Répétitifs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1972

Abstract Soient k un entier positif, X un ensemble et ϕ un homomorphisme du semigroupe libre engendre par X dans le produit direct du groupe cyclique infini par un semi-groupe fini. Il est prouve… Expand

Combinatorics on Words

- Computer Science
- 2004

Words (strings of symbols) are fundamental in computer processing, and nearly all computer software use algorithms on strings. Expand

On uniformly repetitive semigroups

- Mathematics
- 1994

Letk be an integer greater than 1 andS be a finitely generated semigroup. The following propositions are equivalent: 1) the semigroup of non negative integers is not uniformlyk-repetitive; 2) any… Expand