3
$\begingroup$

A k-term combinatorial progression of order d (abbreviated as k-CP(d)) is defined as an integer sequence $x_1 such that the differences between successive numbers are at most d in number, i.e. the set $\{x_{i+1}-x_i:1\le i\le k-1\}$ has cardinality at most d. We say that a set of positive integers A has property CP if, for some fixed d, the set contains a k-CP(d) $\forall k\ge 1$.

A m-cube is defined as a set of the form $=\{a+\sum_{i=1}^m e_iy_i : e_i \in \{0,1\}\}$. We say that a set of positive integers A has the property C if A contains an m-cube $\forall m\ge 1$.

I am trying to establish that $CP\implies C$. The author of the paper I am reading from says it is sufficient to prove the statement: For all $m,d\ge 1$ there exists $r=r(d,m)$ such that if $x_1,x_2\cdots x_r$ is an r-CP(d) then $\{x_1,x_2\cdots x_r\}$ contains an m-cube.

My problem is why is this sufficient to establish this statement? The point I am stuck on is that we are guaranteed a combinatorial progression of a desired length but not guaranteed a combinatorial progression of the desired order. Hence in searching for an m-cube we may only use CP to get r-CP(d') where d' is bigger then d and hence the hypothesis (requisite r-CP(d) forces an m-cube) may not be invoked.

In case anyone is interested this is from an Erdos paper where the author remarks that it is easy to see this. I can't find it easy at all and will be obliged if someone guides me.

Thanks a lot.

1 Answers 1

2

Assume the claim is true, and suppose $A$ has property CP, and we are given some $m \geq 1$. So for some $d \geq 1$, $A$ contains a $k$-CP$(d)$ for all $k \geq 1$. In particular, $A$ contains an $r(d,m)$-CP$(d)$. Hence $A$ contains an $m$-cube, by the claim.

  • 0
    I see that I had misunderstood the definition itself (I was taking d to be dependent on k).2012-05-10