两两 gcd 互异的最大子集大小的上下界分析

· · 算法·理论

给定正整数 m，考虑集合 \{1, 2 \cdots ,m\} 的子集 A，满足对于任意两个不同的无序对 \{a, b\} \neq \{c, d\}，都有 \gcd(a, b) \neq \gcd(c, d)。记 A 的最大大小为 F(m)。

从一些简单的构造入手

一个直观的想法是取质数来保证 \gcd。我们取前 n 个质数的序列。记 P = \prod_{i = 1}^n p_i，可以构造：

a_i = \frac{P}{p_i}, a_n = P

此时:

\gcd(a_i, a_j)= \gcd(\frac{P}{p_i},\frac{P}{p_j}) = \frac{P}{p_ip_j}

显然不同。

此时由素数定理可以得出：

F(m) \ge (1 + o(1))\frac{\log m}{\log\log m}

还能做到比这个更优吗？

链式构造

如果我们只用 2 的幂，那么两个数 \gcd(2^i, 2^j) = 2^{\min(i, j)}。如此对于两对 \gcd(2^1, 2^2) 和 \gcd(2^1, 2^3)，其 \gcd 均为 2^1。

所以一个底的信息不够，我们引入第二个素数 3。

把每个数写为 2^a3^b，这样两个数：

一个很自然的想法是我们钦定上面的式子答案等于 $2^a3^d$，也就是让 $2^a3^b$ 贡献 $2$ 上的指数，$2^c3^d$ 贡献 $3$ 上的指数。 有一个显然的构造是 $2^i3^{n - i}$ 次方，满足如上条件。 这样我们把下界做到了： $$F(m) \ge \Omega(\log m)

那上界呢

要求任意两个不同元素的 \gcd 均不同，我们取出一个元素 a_1，设剩余 n - 1 个数跟其的 \gcd 分别为 d_2, d_3 \cdots d_n。则 d_i 两两不同。

同时 d_i \mid a_1，这相当于要求 a_1 至少有 n - 1 个因数。

我们给出了一个上界：

F(m) \le 1 + \max_{x \le m} \tau(x)

其中 \tau(x) 是 x 的约数个数。

这个问题 \rm Wigert 给出了一个上界：

F(m) \le \exp((\log 2+o(1)\frac{\log m}{\log \log m})

对原问题做一些转化

上界告诉我们，每个元素至多能贡献 \tau(m) 个不同的 \gcd，因此总数受限于最大因子数。 那么一个自然的问题是：能不能构造一个集合，使得每个元素的因子都被充分利用？

将每个整数 a 写成它的素因子集合：

S(a) = \{p : p \mid a\}

那么 S(\gcd(a, b)) = S(a) \cap S(b)

这样问题就变为了：

找一个尽可能大的集合族 \mathcal F \subseteq 2^{[d]}，使得任意两个不同集合的交不同。

随机构造！

取前 d 个质数 p_1 < p_2 < \cdots < p_d。对于 S \subseteq [d]，定义 A(S) = \prod_{t \in S}p_t。

对于每个 i = 1, 2, \cdots N，令 S_i \subseteq [d] 随机生成。这 d 个质数独立以 p 的概率属于 S_i。

这能对？

我们将不合法的集合 S 分为两类：

  2. E_{i, j, k, l} : S_i \cap S_j = S_k \cap S_l

考虑分析这两类的概率。

第一类

考虑一个位置重叠的概率，记：

X_i, X_j, X_k \sim \rm Bernoulli(p)

我们要求 X_iX_j = X_iX_k。

若 X_i = 0，则成立，否则需要 X_j = X_k。故成功概率为 q_1 = (1 - p) + p(p^2 + (1 - p)^2)。而不同位置独立，故：

E_{i, j, k} = ((1 - p) + p(p^2 + (1-p)^2)^d

第二类

同上定义，要求 X_iX_j = X_kX_l，则 q_2 = p^4 + (1 - p^2)^2，有：

E_{i, j, k, l} = (p^4 + (1 - p^2)^2)^d

第一类事件有 3{N \choose 3} 种，第二类有 3{N \choose 4} 种。记 B 是冲突发生的对数，则：

\mathbb E(B) \le 3{N \choose 3}q_1^d+3{N \choose 4}q_2^d

经过简单的分析，第一项更紧，取 p = \frac{2}{3} 可以得到：

\mathbb E(B) \le 3{N \choose 3}\left(\frac{19}{27}\right)^d+3{N \choose 4}\left(\frac{41}{81}\right)^d

全部删掉!

把不合法的 B 个集合集合都删了，剩下的就是一个合法的构造。

所以只需要 B < N 就能找出构造。事实上只需要 \mathbb E(B) = o(N) 即可。

设 N = \lfloor e^{cd}\rfloor，第一项的要求是：

\frac{3{n \choose 3}\left(\frac{19}{27}\right)^d}{N} = O\left(N^2\left(\frac{19}{27}\right)^d\right)

所以只需要 2c + \log\frac{19}{27} < 0，即 c < \frac12\log\frac{27}{19}。

第二类同理得到 c < \frac13\log\frac{81}{41},故：

c < \frac12\log\frac{27}{19}\sim 0.1756

于是像上面一样构造都有 \mathbb E(B) = o(N)，都存在大小至少为：

N - o(N) = \exp\left(\left(\frac12\log\frac{27}{19} - o(1\right))d\right)

的合法族。

而 d 由素数定理是 (1 + o(1))\frac{\log m}{\log\log m} 的。

故我们得到了：

F(m) \ge \exp\left(\left(\frac12\log\frac{27}{19} - o(1)\right)\frac{\log m}{\log \log m}\right)

结论：

\boxed{\exp\left(\left(\frac12\log\frac{27}{19} - o(1)\right)\frac{\log m}{\log \log m}\right) \le F(m)\le \exp\left( \left(\log2+o(1)\right) \frac{\log m}{\log\log m} \right).}

因此目前可以写成

\boxed{ \exp\left( (0.175699-o(1)) \frac{\log m}{\log\log m} \right) \le F(m)\le \exp\left( (0.693147+o(1)) \frac{\log m}{\log\log m} \right). }

后话

这个问题的下界由信息论可以给出 c = \frac{\log 2}{2} \sim 0.3465 的非构造性下界。

本文由 \text{ChatGPT 5.6 Sol} 和 u 群群友给出做法。由 \text{Deepseek v4 pro 0813} 润色。

文字均为笔者所写，保证贡献大于(?) AI。