■整数の表現

【1】2元2次形式による表現と15の定理

 1996年,コンウェイとシュニーバーガーは正定値2元2次形式

  f(x,y)=ax^2+bxy+cy^2=n

が1から15までのすべての整数を表せば,それがすべての整数を表すことを示した(15の定理).

 もっと限定していえば

  1,2,3,5,6,7,10,14,15

の9つの数を表現するならば,すべての整数を表現するという定理である.

 この定理はルジャンドルの4平方和定理「何種類かの4変数2次形式,たとえば,

  x^2+y^2+z^2+mw^2   (m=1,2,3,4,5,6,7)

はすべての正の整数を表現することができる」も内包していて,

  1=1^2,2=1^2+1^2,3=1^2+1^2+1^2,5=2^2+1^2

  6=2^2+1^2+1^2,7=2^2+1^2+1^2+1^2,10=3^2+1^2

  14=3^2+2^2+1^2,15=3^2+2^2+1^2+1^2

 5変数2次形式,たとえば,

  a^2+2b^2+5c^2+5d^2+15e^2

はどの整数も表すことができる.

 それに対して,普遍的な3変数2次形式は存在しない.たとえば,

  f(x,y,z)=x^2+2y^2+yz+4z^2

は1から30までの整数をすべて表すが,31を表すことはできない.他の3元2次形式はこんなにうまい具合にはなっておらず,31以下の整数の中のどれかを表すことができないのである.

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

【2】2元1次形式による表現とシルヴェスターの定理

 互いに素な2つの整数a1,a2が与えられたとき,非負整数が存在して

  m1a1+m2a2=n

が成り立つことは,硬貨の言葉に置き換えるとa1円玉とa2円玉を用いてn円が支払えることを意味する.どの額が支払えるか,支払えない最高額はいくらかという問題が考えられるところである(この問題はフロベニウスの硬貨交換問題と呼ばれる).

 支払えない最高額をフロベニウス数と呼び,g(a1,a2)で表される.

  g(a1,a2)=a1a2−a1−a2=(a1−1)(a2−1)−1

で与えられ,1と(a1−1)(a2−1)の間にある整数のちょうど半数が表現可能である.

 たとえば,a1=4,a2=7の場合,g(a1,a2)=17で,表現不可能な整数の数は(a1−1)(a2−1)/2=9となる.

 シルヴェスターの定理の証明は母関数

  f(z)=1/(1−z^a1)(1−z^a2)z^n

の定数項と関連しているが,硬貨が3枚以上になると格段複雑になり,n元1次形式に対する公式はほとんど成功しなかった.

 なお,n×n正方行列で各行各列の和が同じになるものを半魔方陣Hn,主対角線の和も同じになるものを魔方陣Mnと呼ぶと,それぞれの魔方陣の数も母関数の定数項と関連している.魔方陣の数を数え上げる問題の研究は20世紀になってからようやく始まったものである.→コラム「定数項予想入門」参照

  [参]ベック,ロビンズ「離散体積計算による組合せ数学入門」シュプリンガー・ジャパン

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

【3】レイリーの定理とビーティー数列

 レイリーの定理とは「α,βを1/α+1/β=1を満たす無理数,[]をガウス記号とするとき,2つの数列{an}={[nα]},{bn}={[nβ]}は共通項がなく,併せるとすべての整数1,2,3,・・・を与える.」というものです.

 α≦βとすると,仮定からαは区間(1,2)にあることがわかりますが,たとえば,

  α=(1+√5)/2,β=(3+√5)/2=α+1=α^2

とき,an,bnの値は

n  1  2  3  4  5  6  7  8  9  10

an 1  3 4 6 8 9 11 12 14 16

bn 2 5 7 10 13 15 18 20 23 26

n  11  12  13  14  15  16  17  18  19  20

an 17  19 21 22 24 25 27 29 30 32

bn 28 31 34 36 39 41 44 47 49 52

n  21  22  23  24  25  26  27  28  29  30

an 33  35 37 38 40 42 43 45 46 48

bn 54 57 60 62 65 68 70 73 75 78

n  31  32  33  34  35  36  37  38  39  40

an 50  51 53 55 56 58 59 61 63 64

bn 81 83 86 89 91 94 96 99 102 104

n  41  42  43  44  45  46  47  48  49  50

an 66  67 69 71 72 74 76 77 79 80

bn 107 109 112 115

 これを

n  1  2  3  4  5  6  7  8  9  10

an 1  3 4 6 8 9 11 12 14 16

bn 2 5 7 10 13 15

n  11  12  13  14  15  16  17  18  19  20

an 17  19 21 22 24 25 27 29 30 32

bn 18 20 23 26 28 31

n  21  22  23  24  25  26  27  28  29  30

an 33  35 37 38 40 42 43 45 46 48

bn 34 36 39 41 44 47 49

n  31  32  33  34  35  36  37  38  39  40

an 50  51 53 55 56 58 59 61 63 64

bn 52 54 57 60 62 65

n  41  42  43  44  45  46  47  48  49  50

an 66  67 69 71 72 74 76 77 79 80

bn 68 70 73 75 78

と並べ直すと,2つの数列は共通項がなく,併せるとすべての整数1,2,3,・・・を与えるという意味がおわかり頂けると思います.

 レイリーは数列の任意の連続する2項の間には必ずもう一つの数列の項が入り込むことを発見したのですが,この定理は1962年にビーティーにより再発見されたことにより,2つの数列はビーティー数列と名付けられています.

 数列{an}がビーティー数列ならば,anの値はa1,a2,・・・,an-1の値から1以内の誤差で決定することができます.a1+an-1,a2+an-2,・・・,an-1+a1の和はすべてvまたはv+1になるからです.また,この和がすべてvならばan=v+1でなければなりません.もし,そうでなければビーティー数列ではないということになります.

 たとえば,ビーティー数列1,3,4,6,8,9,・・・において,a1+a1=2よりa2は2または3(実際は3),a1+a2=4よりa3は4または53(実際は4),a1+a3=5,a2+a2=6よりa4は6となります.

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