■差分基底(その1)

p>=2を素数、n=p^2+p+1とする。このとき、0<=a0=0<a1<・・・<ap=<n

すべての1<b<nに対して、b=ai-ajとなるものがある。

===================================

p^3個の要素をもつ有限体GF(p^3)を利用すると証明できるが、さらに

k(n)を[n]の差分基底の最小個数とするとn→∞のとき

k(n)/√n→c、c=[√2,√(8/3)]となる。

===================================

{0,1,4,6}は[6]の差分基底なのでc<=4/√6=√(8/3)

===================================