596 – Continued fractions

October 10, 2011

This term, Summer Hansen is taking a reading course with me on Pell’s equation. Our basic reference is:

  • Jacobson and Williams, Solving the Pell equation. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2009. xx+495 pp. ISBN: 978-0-387-84922-5.

We are allowing a rather organic approach to the material, taking as many detours as it seems appropriate. The topic of continued fractions naturally came up. What follows is just a short compendium of results I found interesting while reading on the subject.

Read the rest of this entry »

496 – Regressive functions on pairs

August 31, 2009

[Updated September 4, 2009.]

(For background, see my paper Regressive functions on pairs, in my papers page.)

Here, {{\mathbb N}=\{0,1,\dots\}.} For {X\subseteq{\mathbb N},} we denote by {X^{[2]}} the set of unordered pairs of elements of {X.} We will use interval notation, with the understanding that our variables range over natural numbers so, for example, {[3,6)=\{3,4,5\}.}

Suppose that {0\notin X.} A function {f:X^{[2]}\rightarrow{\mathbb N}} is regressive iff {f(t)<{\rm min}(t).} We will usually write {f(a,b)} for {f(\{a,b\})} with the understanding that {a<b.}

A subset {H\subseteq X} is min-homogeneous for {f} iff whenever {a<b<c} are in {H,} then {f(a,b)=f(a,c).}

Given {0<n\in{\mathbb N},} denote by {g(n)} the smallest integer {N} such that whenever {f:[n,N]^{[2]}\rightarrow{\mathbb N}} is regressive, there is a min-homogeneous set {H\subset[n,N]} of size at least {4.}

We want to bound the function {g(n)} as precisely as possible.

Here are some exact values and bounds:

  • {g(1)=5.}
  • {g(2)=15.}
  • {g(3)=37.}
  • {g(n)\le 2^{n-1}(n+7)-3.} 
    (In the paper, I prove the weaker bound {g(n)\le 2^n n+12\cdot 2^{n-3}+1} for {n\ge3.})
  • {g(n+1)\ge 2g(n)+3.}

I will be modifying the table above if additional results are found.

Typeset using LaTeX2WP.