Regressive functions on pairs

I recently gave a talk at the Claremont Colleges Algebra/Number Theory/Combinatorics Seminar on the topic of this paper, which can be found in my papers page.

For a set X\subseteq{\mathbb N}^2 let X^{[2]}=\{(n,m)\in X^2:n<m\}. A function f:X^{[2]}\to{\mathbb N} is regressive iff f(u_1,u_2)<u_1 for all u_1<u_2 in X with 0<u_1. A set H\subseteq X is min-homogeneous for f iff f(u,u_1)=f(u,u_2) whenever 0<u<u_1,u_2 and u,u_1,u_2\in H.

Theorem. For all n there exists m such that if X=\{1,2,\dots,m\} and f:X^{[2]}\to{\mathbb N} is regressive, then there is H\subseteq X of size at least n and min-homogeneous for f.

The theorem (due to Kanamori and McAloon) states a version of the classical Ramsey theorem for regressive functions. We cannot expect H to be homogeneous, i.e., in general f\upharpoonright H^{[2]} will not be constant. For example, consider f(u,v)=u-1. Notice also that without loss of generality 1\in H, since f(1,u)=0. It is natural to try to establish the rate of growth of the function g that to each n assigns the least m as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of k variables, Kanamori and McAloon showed:

Theorem. The function g grows faster than any primitive recursive function.

In my paper I show using finite combinatorics methods that g grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function g(n,k) of two variables, defined as g but with the additional requirement that {\rm min}(H)\ge k. Obviously, g(2,k)=k+1 and g(3,k)=2k+1. The situation for g(4,k) is less clear, although it is of exponential growth.

Theorem. We have:

  1. g(4,1)=5, g(4,2)=15, g(4,3)=37, g(4,4)\le85.
  2. 2g(4,m)+3\le g(4,m+1), so g(4,m)\ge 5\times 2^m-3 for m\ge3.
  3. g(4,m+1)\le 2^m(m+2)-2^{m-1}+1.

Question. Does g(4,m)\ge 2^{m-1}m hold?

Although I have not been able to prove this, I do not expect it to be particularly difficult.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: