平方自由整数

Number without repeated prime factors

10 は平方数ではありません。1 より大きい約数は 2、5、10 であり、いずれも平方数ではありません (最初のいくつかの平方数は 1、4、9、16 です)。

√120までの素数の平方倍数を消去した後、120までの平方のない整数が残る。

数学において、平方自由整数（または平方自由整数）とは、1以外の平方数で割り切れない整数のことである。つまり、その素因数分解において、その整数に含まれる素数それぞれに対してちょうど1つの因数が存在する。例えば、10 = 2 ⋅ 5は平方自由整数であるが、18 = 2 ⋅ 3 ⋅ 3 は平方自由整数ではない。なぜなら、18 は9 = 3 ²で割り切れるからである。最小の正の平方自由整数は以下の通りである。

1、2、3、5、6、7、10、11、13、14、15、17、19、21、22、23、26、29、30、31、33、34、35、37、38、39、...（OEISのシーケンスA005117）

平方自由因数分解

すべての正の整数は、という一意の方法で因数分解できます。ここで、と の差は、互いに素な2つの整数からなる平方自由整数です。これは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}}$

あらゆる正の整数は、互いに素であるべき数（すなわち、あらゆる素因数の平方で割り切れる整数）と平方自由整数の積として一意に表すことができます。この因数分解において、平方自由因数は、べき数は、 ${\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 (2s)}},}$

ここでζ ( 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まで（指数を 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}}}$

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

${\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 Q(x)=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor }$

1

${\displaystyle {\begin{aligned}{\phantom {Q(x)}}&=\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)}$

任意の長さの連続する非平方自由整数の列が存在する。実際、異なる素数の組( p ₁ , ..., p _l )のそれぞれに対して、中国剰余定理は同時合同を満たすnの存在を保証する。

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

各n + iはpで割り切れる²
_i^[8]一方、上記の推定は、ある定数cに対して、正のxに対してxと の間に常に平方根のない整数が存在することを意味する。さらに、初等的な議論により、 をで置き換えることができる。^[9] abc予想はを許す。^[10] ${\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)}}$

計算Q ( x )

改良エラトステネスの篩を用いることで、x ≤平方自由整数はÕ ( x )時間で識別・計数できる。Q ( x )のみが必要で、それが計数する数のリストが必要ない場合は、( 1 ) を用いてQ ( x ) をÕ ( √ x )時間で計算できる。Q ( x )の既知の最大値（x = 10 ³⁶ ）は、 2011年に Jakub Pawlewicz によってÕ ( x ^2/5 )時間で計算されたアルゴリズムで、^[11] Õ ( x ^1/3 )時間を要するアルゴリズムが提案されているが実装されていない。^{[12] ： §5.5}

表の質問（×）、⁠6/π ²⁠×、 そしてR（×）

この表は 、 と (後者は小数点第 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 x}$	${\displaystyle Q(x)}$	${\displaystyle {\frac {6}{\pi ^{2}}}x}$	${\displaystyle R(x)}$
10	7	6.1	0.9
10 2	61	60.8	0.2
10 3	608	607.9	0.1
10 4	6,083	6,079.3	3.7
10 5	60,794	60,792.7	1.3
10 6	607,926	607,927.1	−1.3
10 7	6,079,291	6,079,271.0	20.0
10 8	60,792,694	60,792,710.2	−16.2
10 9	607,927,124	607,927,101.9	22.1
10 10	6,079,270,942	6,079,271,018.5	−76.5
10 11	60,792,710,280	60,792,710,185.4	94.6
10 12	607,927,102,274	607,927,101,854.0	420.0
10 13	6,079,271,018,294	6,079,271,018,540.3	−246.3
10 14	60,792,710,185,947	60,792,710,185,402.7	544.3
10 15	607,927,101,854,103	607,927,101,854,027.0	76.0

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

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

2進数としてエンコードする

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

${\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または10進数の11としてエンコードできます。（2進数の桁は、無限積の順序とは逆になります。）

すべての数の素因数分解は一意であるため、平方自由整数のすべての 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 年にAndrás Sárközyによって十分に大きい整数すべてに対して証明され、^[14] 1996 年にOlivier RamaréとAndrew Granvilleによって 4 より大きい整数すべてに対して証明された。^[15]

スクエアフリーコア

約数がt乗でない正の整数を「 t -free」と呼ぶことにする。特に、2-free整数は平方-free整数である。

乗法関数は、 すべての正の整数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)も参照。

注記

1. Adleman, Leonard M.; McCurley, Kevin S. (1994). 「数論的複雑性における未解決問題 II」 Adleman, Leonard M.; Huang, Ming-Deh A. (編).アルゴリズム数論、第1回国際シンポジウム、ANTS-I、ニューヨーク州イサカ、米国、1994年5月6日～9日、議事録. Lecture Notes in Computer Science. Vol. 877. Springer. pp.  291– 322. doi :10.1007/3-540-58691-1_70. ISBN 978-3-540-58691-3。
2. アグラワル、マニンドラ;カヤル、ニーラージ。ニティン、サクセナ（2004 年 9 月 1 日）。 「PRIMES は P にあります」(PDF)。数学年報。160 (2): 781–793。土井: 10.4007/annals.2004.160.781。ISSN  0003-486X。MR  2123939。Zbl 1071.11070  。
3. Richards, Chelsea (2009). 有限体上の平方自由多項式の因数分解アルゴリズム(PDF) (修士論文). カナダ: サイモンフレーザー大学.
4. Walfisz、A. (1963)。Weylsche Exponentialsummen in der neueren Zahlentheorie。ベルリン: VEB Deutscher Verlag der Wissenschaften。
5. ジア、チャオファ。 「自由平方数の分布」、中国の科学シリーズ A: 数学 36 :2 (1993)、154 ～ 169 ページ。 Pappalardi 2003、A Survey on k-freeness で引用。また、Kaneenika Sinha、「特定の算術関数の平均次数、2012 年 2 月 14 日にウェイバック マシンにアーカイブ」、Journal of the Ramanujan Mathematical Society 21 :3 (2006)、267 ～ 277 ページも参照してください。
6. Liu, H.-Q. (2016). 「平方自由数の分布について」.数論ジャーナル. 159 : 202– 222. doi : 10.1016/j.jnt.2015.07.013 .
7. リンフット、EH ;エヴリン、CJA (1929 年)。 「数の加法理論の問題について」。数学的ツァイシュリフト。30 : 443–448。土井:10.1007/BF01187781。S2CID  120604049。
8. ペアレント, DP (1984). 数論演習. 数学の問題集.シュプリンガー・フェアラークニューヨーク. doi :10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9。
9. フィラセタ, マイケル; トリフォノフ, オグニアン (1992). 「平方自由数間のギャップについて. II」.ロンドン数学会誌. 第2シリーズ. 45 (2): 215– 221. doi :10.1112/jlms/s2-45.2.215. MR  1171549.
10. グランビル、アンドリュー(1998). 「ABC によりスクエアフリーを数えることができる」. Int. Math. Res. Not . 1998 (19): 991– 1009. doi :10.1155/S1073792898000592.{{cite journal}}: CS1 maint: unflagged free DOI (link)
11. Pawlewicz, Jakub (2011). 「平方自由数の計算」. arXiv : 1107.4890 [math.NT].
12. ハーシュ、ディーン;ケスラー、イド;メンドロビッチ、ウリ (2024)。 「π(N) の計算: Õ(√N) 時間での基本的なアプローチ」。計算の数学。arXiv : 2212.09857。土井：10.1090/mcom/4039。ISSN  0025-5718。
13. 田中実 (1979). 「平方自由数の分布に関する実験」.日本学士院紀要, シリーズA, 数学科学. 55 (3). doi : 10.3792/pjaa.55.101 . S2CID  121862978.
14. Sárközy, A. (1985). 「二項係数の約数について. I.」. Journal of Number Theory . 20 (1): 70– 80. doi : 10.1016/0022-314X(85)90017-4 . MR  0777971.
15. Ramaré, Olivier; Granville, Andrew (1996). 「指数和の明示的境界と平方自由二項係数の希少性」Mathematika . 43 (1): 73– 107. doi :10.1112/S0025579300011608.

参考文献

• シャピロ、ハロルド・N. (1983). 『数論入門』オックスフォード大学出版局Dover Publications. ISBN 978-0-486-46669-9。
• グランヴィル、アンドリュー；ラマレ、オリヴィエ (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. Zbl  1058.11001。
• 「OEIS Wiki」 。 2021年9月24日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Square-free_integer&oldid=1319921998"