n=17正方形装填的又一个更优下界

# n=17正方形装箱的又一个更优下界 来源：http://gus-massa.blogspot.com/2026/08/another-better-lower-bound-for-n17.html 本研究旨在改进最新成果，并利用以下权重证明 4\.5058\(?\)≤s\(17\)： [](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhRaVBVeRCHcmLXqXc7DMViLHlxO35_qb0A5Pw8Bk94zlR-AujKaJQueGQKmL0mDBZZL20sUiYLpH5udzojy2eZKJlD9JvpABHdcXvLFjdGzpH-TVkheY4YdHQOTDd-K4UkCc3n9daAD1o99hBXsxMOWILLwN0kyY4L2cwBTrC-nRKBsG0Sa6gNdYXact3i/s406/S17-Massaccesi.png) 但首先定义 s\(17\)。引用该主题的旧文章 (https://erich-friedman.github.io/papers/squares/squares.html) *设 s(n) 为能够装入 n 个单位正方形的最小正方形的边长。* 对于 n=16，显然最佳方案是 4x4 阵列，因此 s\(16\)=4。对于 n=15，15 个单位正方形同样可显而易见地放入 4x4 正方形，故 s\(15\)≤4。证明其为更小正方形则绝非易事。无论如何，Erich Friedman 在 1999 年证明了该结论，因此 s\(15\)=4。 对于 n=17，显然的包围正方形是 5x5，但在 1998 年 John Bidwell 发现了一个实例，表明边长为 4\.6756... 的正方形即足够，故 s\(17\)≤4\.6756...。这是一种非常有趣的正方形排列方式，值得查阅相关收藏进行查看 (https://kingbird.myphotos.cc/packing/squares_in_squares.html) 以及其他数字的版本。 另一方面，Trevor Green 在 2000 年证明了 4\.4452...≤s\(17)（更多细节见后文）。因此曾存在巨大的差距：4\.4452...≤s\(17)≤4\.6756...。 几周前，Sam Burns 利用 ChatGPT 5\.6 改进（？）了下界 (https://sam-burns.com/posts/proposing-better-lower-bound-for-n17-square-packing/)。新边界尚未经过社区审阅。我查看后认为其非常合理且可能正确，但可能在证明或配套程序中遗漏了小的边界情况，或是存在巨大漏洞。为保险起见，我在数字后添加小号（？）标注，但对此正确性相当乐观和自信，因此仅使用半号字体。 当前边界为 4\.4452...≤4\.4811\(?\)≤s\(17)≤4\.6756...。 我对 Sam Burns 的主要异议是其确实值得配有精良图示！因此我的首要步骤是为此添加优质图表。 同时，在改进程序过程中，我发现了新的下界 4\.5058。 因此现在我们有：4\.4452...≤4\.4811\(?\)≤4\.5058\(?\)≤s\(17)≤4\.6756...。 我的新示例及代码修改在此，但关于发现新边界的技术细节见第二篇文章 (https://gus-massa.blogspot.com/2026/08/linear-programing-for-square-packing.html)。 ## Trevor Green 的边界 Trevor Green 旧证明 (19+40\*sqrt\(2\))/17≅4\.4452...≤s\(17) 的思路是在边长 4\.4452... 的正方形中选取 16 个非常有趣的“不可避免”点，然后运用大量几何学证明任意单位正方形必须包含其中至少一点。因此若试图在此放入 17 个单位正方形，至少有两个正方形必须共享这 16 个有趣点之一。 该构造从 4x6 网格中选取 16 个点。我仅在旧文章 (https://erich-friedman.github.io/papers/squares/squares.html) 找到点的图像，但未找到解析定义。通过观察正方形边长公式、使用标尺并结合猜测，我认为空左右边距为 0\.5，空上下边距为 sqrt\(2\)\-1/2≅0\.9142...。 在此选择下，原图中的对角线段长度为 1，这是构建以不可避免点为顶点的三角形的极有用数值。（欢迎确认。） 它使用 6x4 网格，空边距为 0\.9142... 和 0\.5000，网格总尺寸为 2\.6168... 和 2\.4452...。 [](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2jEwWVFRox7KC_zJtI2STGWUx6lbOxlSwpcRcAjU94QAZHR3-DudMOmefgec6dMyDl2TIdgvPDQ4MJztW2ln4YsW8K58r2E-432nNnDsdSnKTZk3uKpc4_yInC_kueyzkIGouDIbgjhX9Pt1GHj_bt5ZNwh3RSLvUvICdDhHkPe8qOp4ClA8Zk7PhyphenhyphenVhN/s406/image1787327365) 为将该构造与更新构造对比，最好将其对称化。在此对称版本中，每个单位正方形包含至少 4 个点，但部分点较粗，计为双重点（更多细节见后）。 [](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNpkVv-KUaqNYcMAtNqoF0mLzQT9DO1uXFw2fHggJBWdqWtZP8AtZ8m6SCHmENHg_-MfmPKx53X7TuuxNSnEyTxKxTBSzjWzhukcjiaVSd8ASJE94vmr4UT8IdRLWUKPfdkBSEt3dYejGA_KCZrdSRJQ_8GKGFHmykQz08Ls05s8h85WKAnZbSNbSoFKJN/s406/S17-Green-S.png) ## Sam Burns 的边界 Sam Burns 发布的证明 4\.4811\(?\)≤s\(17) 方法 (https://sam-burns.com/posts/proposing-better-l-bound-for-n17-square-packing/) 使用 ChatGPT 在边长 4\.4811 的正方形中选取 268 个较有趣的点。 这些点具有不同权重，总权重仅为 16\.9476。经简化后仅需测试有限方向，他们使用 Python (https://www.python.org/) 程序测试“所有”可能的“近似单位”（实际为 \.9973）正方形，并验证每个正方形内的权重和至少为 1（实际 1\.0003）。因此若试图在此放入 17 个单位正方形，至少有两个正方形必须共享这 268 个较有趣点中的至少一个。（更多细节见第二篇文章 (https://gus-massa.blogspot.com/2026/08/linear-programing-for-square-packing.html)。） 此方法存在漏报。若程序验证通过则肯定正确，但若失败则存在极小错误概率。这对确保权重证明下界是可接受的。 [](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhg2YeOFAMClHEPVAlx_0AiFD_Gb-FLiSBpHNeZbPLKjMZr0zYPq-wgo-CLYx-fLylBFmGNfXCANtIXEj2ZHBDxKc6M37SJwi18BYqUe3KjphWzbPwV9E42W1zr-eS9qol6QuqfVr467af_FrgtprYxEzGL2x_MizWNvaHtj77ip4VCwwxB2aSr24weEwy_/s406/S17-Burns.png) 尚不清楚权重如何选择。将此解与旧文章所有示例 (https://erich-friedman.github.io/papers/squares/squares.html) 对比，0\.5 边距过窄，因大多数示例使用约 1\.0 或 9\.1 等。权重选择与我一致，且网格首/末行/列的所有权重均为零。 依我粗略见解，次首/次末行/列也应为空，但网格 \(1, 11\) 及其对称像中存在非零权重，希望在更优示例中无需此点。第三/倒数第三行/列相当充实。它比旧示例更接近边界，因此在边界附近添加更多点似乎是改进边界的良策。 我使用 Racket (https://racket-lang.org/) 配合 Metapict (https://docs.racket-lang.org/metapict/) 包绘制图像。每个圆的半径根据权重计算为 r = sqrt\(weight^\(1/gamma\)\) \* scale 当 gamma = 1\.0 时面积与权重成正比，但小权重在图像中过小。经调整后 gamma=2\.0 效果良好，因小权重更易辨识。scale 并非神秘，我本应在其中使用 π，但 scale=0\.07 在我的设备上效果良好。 圆为半透明，因此若放大 scale 可观察重叠情况。代码位于底部，并将权重除以实际最小和 1\.0003。 ## 新边界 我的思路是尝试边距和内部网格尺寸的不同组合。如前所述，尚不清楚 Sam Burns 示例中权重如何选择。因此对于每个固定尺寸，我决定使用线性规划 (https://en.wikipedia.org/wiki/Linear_programming) 来确定权重。随后我结合暴力搜索与运气找到最优网格。之后我舍入权重使其美观且为简易分数。（更多细节见第二篇文章 (https://gus-massa.blogspot.com/2026/08/linear-programing-for-square-packing.html)。） 经过长时间尝试，我得到的最佳结果为 4\.5058\(?\)≤s\(17)。新解在边长 4\.5058 的正方形中使用 168 个较有趣点，构成 29x29 网格。它们总和仅为 16\.9166...。每个单位正方形包含的总权重至少为 1。 存在空边距 0\.77565，内部网格总边长为 3\.9545。 [](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6QwquQQfC-6AQmNzeez3ppudQz1Wz9B1vMvvo9rI-RnoC66THTq1fpTc7XAn0qDYXrixbJdb2PWFMagraUToVRaiRAgs4Ax-WDAbFIKdQ5PvglQJ9IKYf-_v3k7gT_ZRBGGn2pKuUsxVT_v5pVKeAai3fVPxWJGZdpjiC_fAYJ5XYsUnOE0il_6cEmUas/s406/image1787327336) 如前所述，权重比观察旧示例时更接近边界，接近之前次首/次末行/列。它还使用更少权重，因此希望无需计算机即可证明其正确性。 我想制作非对称版本，可能更优。Sam Burns 发布的程序假设空边距为 0\.5，因此我稍作修改以允许可变边距 M（边距的两倍）。包含该修改、新尺寸和新权重表的版本位于底部。运行该程序并修改 Sam Burns 发布的说明 (https://sam-burns.com/posts/proving-better-lower-bound-for-n17-square-packing/) 即可证明（？）新边界。 ## 结论与未来工作 - 分布在角落相当离散，但中心附近存在奇怪条形。增加网格尺寸并观察将很有意义。同时，窄空边距似乎有用。 - 我在第二篇文章中的搜索程序过慢（约 1 小时），因此避免改变网格尺寸。探索其他网格尺寸可能因有趣巧合而有用。 - 添加更多数字仅需几分钟，我未费心，因细化网格或增加旋转方向似乎会产生更大变化。 - 此结果也自动改进了 s\(18)、s\(19) 和 s\(20) 的下界。但对这些数值的更深入搜索应能提供更优边界。我见过太多权重总和为 18 的案例。数字 18 存在有趣之处。 - 我想找到非对称版本。我有一些思路待尝试，因此请隔日再访。非对称版本有望拥有约 1/8 的权重，并有望展示近似等边三角形，且无需计算机更易理解。 您可能想阅读第二篇文章 (https://gus-massa.blogspot.com/2026/08/linear-programing-for-square-packing.html)，其中包含如何获得新权重的详细信息。 ## 验证边界程序 ```python from __future__ import annotations from bisect import bisect_left, bisect_right from fractions import Fraction as F import numpy as np # Sam Burns 2026 发布的原始版本 # Gustavo Massaccesi 2026 修改版 # 提议的精确下界证书，用于装入 17 个单位正方形的正方形。 # 所有几何量与谓词均为有理数。NumPy 仅用于整数范围加法与累积和；不使用浮点几何。 L = F(45058, 10000) # 正方形边长 M = F(15513, 10000) # 两侧空边距 B = F(9973, 10000) T = F(207107, 500000) KMAX = 180 D = T / KMAX WEIGHT_SCALE = 576 # 最小权重 NGRID = 29 LAST = NGRID - 1 # (i, j, w)：网格点 (i,j) 的每个不同 D4 像素获得权重 w/WEIGHT_SCALE。 CERT = [ (0, 2, 165), (0, 11, 129), (1, 8, 36), (1, 10, 21), (1, 11, 15), (2, 2, 246), (2, 8, 129), (2, 9, 105), (2, 10, 36), (2, 11, 105), (5, 10, 36), (6, 10, 63), (6, 11, 12), (7, 10, 21), (8, 9, 33), (8, 11, 15), (9, 11, 75), (9, 14, 39), (10, 11, 25), (10, 12, 21), (10, 13, 24), (10, 14, 3), (11, 11, 16) ] def orbit(i: int, j: int) -> set[tuple[int, int]]: n = LAST return { (i, j), (n - i, j), (i, n - j), (n - i, n - j), (j, i), (n - j, i), (j, n - i), (n - j, n - i), } def build_atoms() -> list[tuple[F, F, int]]: step = (L - M) / LAST coord = [M / 2 + step * i for i in range(NGRID)] by_index: dict[tuple[int, int], int] = {} for i, j, w in CERT: for ij in orbit(i, j): if ij in by_index: raise ValueError(f"duplicate orbit assignment at {ij}") by_index[ij] = w return [ (coord[i], coord[j], w) for (i, j), w in sorted(by_index.items()) ] # 将有理凸多边形剪裁至 U >= bound 或 U <= bound。 def clip_u(poly: list[tuple[F, F]], bound: F, keep_ge: bool) -> list[tuple[F, F]]: if not poly: return [] out: list[tuple[F, F]] = [] def inside(p: tuple[F, F]) -> bool: return p[0] >= bound if keep_ge else p[0] <= bound prev = poly[-1] prev_in = inside(prev) for cur in poly: cur_in = inside(cur) if cur_in != prev_in: u1, v1 = prev u2, v2 = cur if u2 == u1: v = v1 else: lam = (bound - u1) / (u2 - u1) v = v1 + lam * (v2 - v1) out.append((bound, v)) if cur_in: out.append(cur) prev, prev_in = cur, cur_in return out def center_domain(c: F, s: F) -> list[tuple[F, F]]: # 方向为 (c,s) 的 B-正方形位于 [0,L]^2 当其中心位于 [h,L-h]^2，其中 h=B(c+s)/2。 # 将该正方形变换至 B-正方形的 (U,V) 框架。 h = B * (c + s) / 2 lo, hi = h, L - h corners_xy = [(lo, lo), (hi, lo), (hi, hi), (lo, hi)] return [(c * x + s * y, -s * x + c * y) for x, y in corners_xy] def verify_orientation(c: F, s: F, atoms: list[tuple[F, F, int]]) -> int: """返回一个有理方向的精确最小整数分数。""" half = B / 2 dom = center_domain(c, s) u_dom_min = min(u for u, _ in dom) u_dom_max = max(u for u, _ in dom) v_dom_min = min(v for _, v in dom) v_dom_max = max(v for _, v in dom) rects: list[tuple[F, F, F, F, int]] = [] u_events = {u_dom_min, u_dom_max} v_events = {v_dom_min, v_dom_max} # 在中心坐标中，原子成员资格为轴对齐矩形。 for x, y, w in atoms: pu = c * x + s * y pv = -s * x + c * y u1, u2 = pu - half, pu + half v1, v2 = pv - half, pv + half rects.append((u1, u2, v1, v2, w)) u_events.add(u1) u_events.add(u2) v_events.add(v1) v_events.add(v2) ue = sorted(u_events) ve = sorted(v_events) ui = {x: i for i, x in enumerate(ue)} vi = {x: i for i, x in enumerate(ve)} # 精确整数二维差分数组。分数在每个开放事件单元中恒定。 # NumPy 此处仅执行整数运算。 diff = np.zeros((len(ue), len(ve)), dtype=np.int64) for u1, u2, v1, v2, w in rects: a, b = ui[u1], ui[u2] p, q = vi[v1], vi[v2] diff[a, p] += w diff[b, p] -= w diff[a, q] -= w diff[b, q] += w scores = diff.cumsum(axis=0).cumsum(axis=1) nu, nv = len(ue) - 1, len(ve) - 1 best = 10**18 for i in range(nu): u0, u1 = ue[i], ue[i + 1] if u1 <= u_dom_min or u0 >= u_dom_max: continue slab = clip_u(dom, u0, True) slab = clip_u(slab, u1, False) if not slab: continue vlo = min(v for _, v in slab) vhi = max(v for _, v in slab) if vhi <= vlo: continue # 此操作可能检查可行事件单元的超集，对下界验证是保守的。 j0 = max(0, bisect_right(ve, vlo) - 1) j1 = min(nv - 1, bisect_left(ve, vhi) - 1) if j0 <= j1: row_min = int(scores[i, j0:j1 + 1].min()) best = min(best, row_min) if best == 10**18: raise RuntimeError("center domain was not enumerated") return best def angle_net() -> list[tuple[F, F]]: out: list[tuple[F, F]] = [] for k in range(KMAX + 1): t = T * k / KMAX den = 1 + t * t c = (1 - t * t) / den s = 2 * t / den assert c * c + s * s == 1 out.append((c, s)) # 最终相邻对包含 π/4。 assert out[-2][1] < out[-2][0] assert out[-1][1] >= out[-1][0] # 若 psi_k=2 arctan(t_k)，相邻角间隙的一半为 # arctan(t_{k+1})-arctan(t_k)，其正切值为 # D/(1+t_k*t_{k+1}) <= D。因此 [0,pi/4] 中每个角 # 与网络方向的误差 epsilon < D。 for k in range(KMAX): t0 = T * k / ```