A k-term combinatorial progression of order d (abbreviated as k-CP(d)) is defined as an integer sequence $x_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.
Combinatorial progressions and cubes
3
$\begingroup$
combinatorics
elementary-set-theory
1 Answers
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.
-
0I see that I had misunderstood the definition itself (I was taking d to be dependent on k). – 2012-05-10