平方のない整数

数学において、平方自由整数（または平方自由整数）は、1以外の平方数で割り切れない整数である。つまり、その素因数分解では、その整数に含まれる素数ごとにちょうど1つの因数を持つ。たとえば、10 = 2 ⋅ 5は平方自由だが、18 = 2 ⋅ 3 ⋅ 3 は平方自由ではない。18 は9 = 3 ²で割り切れるからである。最小の正の平方自由数は、

すべての正の整数は、という一意の方法で因数分解できます 。 ここで、 1 と異なる は、互いに素な2 対 1である平方自由整数です。これをnの平方自由因数分解と呼びます。 ${\displaystyle n}$$${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$${\displaystyle q_{i}}$

平方自由因数分解を構成するには、 を の素因数分解 とします。ここで は異なる素数です。平方自由因数分解の因数は次のように定義されます。 $${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$$${\displaystyle n}$${\displaystyle p_{j}}$$${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$$

整数が平方数でないのは、すべての に対して である場合に限ります。1 より大きい整数が別の整数の 乗である場合に限り、すべての の約数であり、${\displaystyle q_{i}=1}$${\displaystyle i>1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle i}$${\displaystyle q_{i}\neq 1.}$

整数の二乗なし因数分解の使用は、その計算が素因数分解の計算と同じくらい難しいという事実によって制限されます。より正確には、二乗なし因数分解を計算する既知のアルゴリズムはすべて、素因数分解も計算します。これは、同じ定義を与えることができる多項式の場合との顕著な違いですが、この場合、二乗なし因数分解は完全な因数分解よりも計算が簡単なだけでなく、すべての標準的な因数分解アルゴリズムの最初のステップです。

整数の根号は、前のセクションの表記法に従うと、その整数の最大の平方自由因数です。整数が平方自由であるのは、その根号と等しい 場合のみです。${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}}$

あらゆる正の整数は、互いに素であるべき数（つまり、あらゆる素因数の2乗で割り切れる整数）と平方のない整数の積として一意に表すことができます。この因数分解では、平方のない因数は、べき数は、${\displaystyle n}$${\displaystyle q_{1},}$${\displaystyle \textstyle \prod _{i=2}^{k}q_{i}^{i}.}$

の平方自由部分はであり、これは と互いに素であるの最大の平方自由約数である。整数の平方自由部分は、最大の平方自由約数よりも小さい場合がある。${\displaystyle n}$${\displaystyle q_{1},}$${\displaystyle k}$${\displaystyle n}$${\displaystyle n/k}$${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}.}$

任意の正の整数は、平方数と平方数でない整数 の積として一意に表すことができます。 この因数分解では、はの最大の約数であり、 は の約数です。 ${\displaystyle n}$$${\displaystyle n=m^{2}k}$$${\displaystyle m}$${\displaystyle n}$${\displaystyle m^{2}}$${\displaystyle n}$

まとめると、あらゆる整数に自然に関連付けられている 3 つの平方自由因数があります。平方自由部分、上記の因数、および最大の平方自由因数です。それぞれが次の因数です。すべては素因数分解または平方自由因数分解から簡単に演繹できます。 が の 素因数分解および平方自由因数分解である場合( は異なる素数)、平方自由部分は です。 商が平方になるような平方自由因数は であり 、最大の平方自由因数は です。 ${\displaystyle k}$$${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$$${\displaystyle n}$${\displaystyle p_{1},\ldots ,p_{h}}$$${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$$$${\displaystyle \prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},}$$$${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$$

たとえば、平方部分が7の場合、商が平方になる平方無料因数は3 ⋅ 7 = 21であり、最大の平方無料因数は2 ⋅ 3 ⋅ 5 ⋅ 7 = 210です。 ${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$

これらの平方なし因数のいずれかを計算するためのアルゴリズムで、完全な素因数分解を計算するよりも高速なものは知られていない。特に、整数の平方なし部分を計算する多項式時間アルゴリズム、あるいは整数が平方なしかどうかを判断する ための多項式時間アルゴリズムは知られていない。 ^{[1]対照的に、}素数判定では多項式時間アルゴリズムが知られている。^[2]これは、整数の算術と一変数多項式の算術の主な違いであり、多項式の無料平方因数分解では多項式時間アルゴリズムが知られている（つまり、多項式の最大の平方なし因数は、多項式とその形式導関数の最大公約数による商である）。^[3]

正の整数が平方数でないのは、を素因数分解したときに指数が 1 より大きい素因数が発生しない場合に限ります。同じことを別の言い方で言うと、のすべての素因数について、その素因数はを均等に割り切れないという ことです。また、 が平方数でないのは、 のすべての因数分解において、因数と が互いに素である場合に限ります。この定義から直接得られる結果は、すべての素数が平方数でないということです。 ${\displaystyle n}$${\displaystyle n}$ ${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n/p}$${\displaystyle n}$${\displaystyle n=ab}$${\displaystyle a}$${\displaystyle b}$

正の整数が平方数を持たないのは、位数のすべてのアーベル群が同型である場合に限ります。これは、そのような群が巡回 である場合に限ります。これは、有限生成アーベル群の分類から得られます。 ${\displaystyle n}$ ${\displaystyle n}$

整数が平方数でないのは、因数環（モジュラー算術を参照）が体の積である場合に限ります。これは、中国剰余定理と、形式の環が体であるための必要条件が が素数である場合に限り、という事実から導かれます。 ${\displaystyle n}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /k\mathbb {Z} }$${\displaystyle k}$

任意の正の整数 に対して、 のすべての正の約数の集合は、整列性を順序関係として使用すると、半順序集合になります。この半順序集合は常に分配格子です。 が平方自由である 場合に限り、これはブール代数です。${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

正の整数が平方数でないのは、 の場合のみであり、 はメビウス関数を表します。 ${\displaystyle n}$ ${\displaystyle \mu (n)\neq 0}$${\displaystyle \mu}$

メビウス関数の絶対値は、平方根のない整数の指示関数である。つまり、| μ ( n ) | は、 nが平方根のない整数であれば 1 に等しく、そうでない場合は 0 になる。この指示関数の ディリクレ級数は、

${\displaystyle \sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta (s)}{\zeta (2秒)}},}$

ここでζ ( s )はリーマンゼータ関数である。これはオイラー積から導かれる。

${\displaystyle {\frac {\zeta (s)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{-s})}}=\prod _{p}(1+p^{-s}),}$

ここで、積は素数に対して取られます。

Q ( x ) は 1 からxまでの間の平方でない整数の数を表します( OEIS : A013928指数を 1 ずつシフトします)。nが大きい場合、 n未満の正の整数の 3/4 は4 で割り切れず、これらの数の 8/9 は 9 で割り切れません。これらの比は乗法性を満たすため(これは中国剰余定理に従います)、近似値が得られます。

${\displaystyle {\begin{aligned}Q(x)&\approx x\prod _{p\ {\text{prime}}}\left(1-{\frac {1}{p^{2}}}\right)=x\prod _{p\ {\text{prime}}}{\frac {1}{(1-{\frac {1}{p^{2}}})^{-1}}}\\&=x\prod _{p\ {\text{prime}}}{\frac {1}{1+{\frac {1}{p^{2}}}+{\frac {1}{p^{4}}}+\cdots }}={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}}}={\frac {x}{\zeta (2)}}={\frac {6x}{\pi ^{2}}}.\end{aligned}}}$

この議論は、推定値を得るために厳密に行うことができます（ビッグO記法を使用）

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left({\sqrt {x}}\right).}$

証明の概要：上記の特徴から、

${\displaystyle Q(x)=\sum _{n\leq x}\sum _{d^{2}\mid n}\mu (d)=\sum _{d\leq x}\mu (d)\sum _{n\leq x,d^{2}\mid n}1=\sum _{d\leq x}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor ;}$

の最後の加数がゼロであることに注目すると、 ${\displaystyle d>{\sqrt {x}}}$

${\displaystyle {\begin{aligned}Q(x)&=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor =\sum _{d\leq {\sqrt {x}}}{\frac {x\mu (d)}{d^{2}}}+O\left(\sum _{d\leq {\sqrt {x}}}1\right)=x\sum _{d\leq {\sqrt {x}}}{\frac {\mu (d)}{d^{2}}}+O({\sqrt {x}})\\&=x\sum _{d}{\frac {\mu (d)}{d^{2}}}+O\left(x\sum _{d>{\sqrt {x}}}{\frac {1}{d^{2}}}+{\sqrt {x}}\right)={\frac {x}{\zeta (2)}}+O({\sqrt {x}}).\end{aligned}}}$

リーマンゼータ関数の最大の零点のない領域を利用することで、アーノルド・ウォルフィスは近似を^{[4]に改良した。}

${\displaystyle Q(x)={\frac {6x}{\pi ^{2}}}+O\left(x^{1/2}\exp \left(-c{\frac {(\log x)^{3/5}}{(\log \log x)^{1/5}}}\right)\right),}$

ある正の定数cに対して。

リーマン予想の下では、誤差項は^[5]に減少する。

${\displaystyle Q(x)={\frac {x}{\zeta (2)}}+O\left(x^{17/54+\varepsilon }\right)={\frac {6}{\pi ^{2}}}x+O\left(x^{17/54+\varepsilon }\right).}$

2015年には誤差項はさらに減少し（リーマン予想も仮定して）^[6]

${\displaystyle Q(x)={\frac {6}{\pi ^{2}}}x+O\left(x^{11/35+\varepsilon }\right).}$

したがって、平方数でない数の 漸近的/自然密度は

${\displaystyle \lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{2}}}\approx 0.6079}$

したがって、整数の 3/5 以上は平方数ではありません。

同様に、Q ( x , n )が1とxの間のn自由整数（例えば3自由整数は立方体自由整数）の数を表す場合、^[7]

${\displaystyle Q(x,n)={\frac {x}{\sum _{k=1}^{\infty }{\frac {1}{k^{n}}}}}+O\left({\sqrt[{n}]{x}}\right)={\frac {x}{\zeta (n)}}+O\left({\sqrt[{n}]{x}}\right).}$

4 の倍数は必ず平方因数 4=2 ²を持つので、連続する 4 つの整数がすべて平方でないということは起こり得ません。一方、4 n +1、4 n +2、4 n +3 がすべて平方でない整数nは無限に存在します。そうでない場合、十分に大きい n に対して 4 n と 4 n +1、4 n +2、4 n +3 の少なくとも 1 つが平方でない可能性があることを考慮すると、すべての正の整数の半分から有限個を引いたものは平方でないはずであり、したがって

${\displaystyle Q(x)\leq {\frac {x}{2}}+C}$ある定数Cに対して、

上記の漸近推定値とは反対に。 ${\displaystyle Q(x)}$

任意の長さの連続する非平方整数の列が存在する。実際、nが同時合同性を満たす 場合

${\displaystyle n\equiv -i{\pmod {p_{i}^{2}}}\qquad (i=1,2,\ldots ,l)}$

異なる素数 に対して、それぞれはp _i ²で割り切れる。^[8]一方、上記の推定は、ある定数cに対して、正のxに対して、 xと の間に平方のない整数が常に存在することを意味します。さらに、基本的な議論により、を で置き換えることができます。 ^[9] ABC予想はを許容します。^[10]${\displaystyle p_{1},p_{2},\ldots ,p_{l}}$${\displaystyle n+i}$${\displaystyle Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+c{\sqrt {x}}}$${\displaystyle x+cx^{1/5}\log x.}$${\displaystyle x+x^{o(1)}}$

この表は 、 と (後者は小数点第 1 位に丸められています) を 10 の累乗で比較したものです。 ${\displaystyle Q(x)}$${\displaystyle {\frac {6}{\pi ^{2}}}x}$

${\displaystyle R(x)=Q(x)-{\frac {6}{\pi ^{2}}}x}$とも表記されます。 ${\displaystyle \Delta (x)}$

${\displaystyle R(x)}$無限大に近づくにつれて、その符号は無限に変化する。^[11]${\displaystyle x}$

の絶対値はと比較すると驚くほど小さいです。 ${\displaystyle R(x)}$${\displaystyle x}$

平方数を無限積として表すと

${\displaystyle \prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ and }}p_{n}{\text{ is the }}n{\text{th prime}},}$

そして、それらを2進数のビットとして使い、エンコードする。 ${\displaystyle a_{n}}$

${\displaystyle \sum _{n=0}^{\infty }{a_{n}}\cdot 2^{n}.}$

平方数 42 は、因数分解すると2 × 3 × 7となり、無限積として2 ¹ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ⁰ ···となります。 したがって、数 42 は、2 進数シーケンス...001011または 11 10 進数としてエンコードできます。(2 進数の桁は、無限積の順序とは逆になります。)

すべての数の素因数分解は一意であるため、平方のない整数のすべての 2 進エンコードも一意です。

逆もまた真なりです。すべての正の整数は一意のバイナリ表現を持つため、このエンコードを逆にして一意の平方フリー整数にデコードすることが可能です。

また、たとえば、42 という数字を、今度は単純に正の整数として扱うと、その 2 進表現が得られます。これは、 2 ⁰ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ¹ = 3 × 7 × 13 = 273101010とデコードされます。

したがって、平方自由数のバイナリ符号化は、非負整数と正の平方自由整数の集合との間の 一対一表現を表します。

（ OEISの配列A019565、A048672、A064273を参照。）

中心二項係数

${\displaystyle {2n \choose n}}$

n > 4の場合には平方根は決して生じない。これは1985年にアンドラーシュ・サルコジ^[12]によって十分に大きい整数すべてに対して証明され、1996年にはオリヴィエ・ラマレとアンドリュー・グランヴィル^[13]によって4より大きい整数すべてに対して証明された。

約数がt乗でない正の整数を「 tフリー」と呼びます。特に、2 フリー整数は平方フリー整数です。

乗法関数は、 すべての正の整数nを、その最大の約数であるt乗で割った商にマッピングします。つまり、 ${\displaystyle \mathrm {core} _{t}(n)}$

${\displaystyle \mathrm {core} _{t}(p^{e})=p^{e{\bmod {t}}}.}$

整数はt自由であり、すべてのt自由整数は関数によってそれ自身にマッピングされる。${\displaystyle \mathrm {core} _{t}(n)}$${\displaystyle \mathrm {core} _{t}.}$

この数列の ディリクレ生成関数は ${\displaystyle \left(\mathrm {core} _{t}(n)\right)_{n\in \mathbb {N} }}$

${\displaystyle \sum _{n\geq 1}{\frac {\mathrm {core} _{t}(n)}{n^{s}}}={\frac {\zeta (ts)\zeta (s-1)}{\zeta (ts-t)}}}$。

OEIS :A007913 ( t =2)、OEIS :A050985 ( t =3)、OEIS :A053165 ( t =4)も参照。

• シャピロ、ハロルド・N. (1983)。数論入門。オックスフォード大学出版局ドーバー出版。ISBN 978-0-486-46669-9。
• Granville, Andrew; Ramaré, Olivier (1996). 「指数和の明示的境界と平方自由二項係数の希少性」. Mathematika . 43 : 73–107. CiteSeerX  10.1.1.55.8 . doi :10.1112/S0025579300011608. MR  1401709. Zbl  0868.11009.
• ガイ、リチャード K. (2004)。数論における未解決問題(第 3 版)。Springer - Verlag。ISBN 978-0-387-20860-2.ZBL1058.11001  。​
• 「OEIS Wiki」 。 2021年9月24日閲覧。