Another Better Lower Bound for N=17 Square Packing

Aug 21, 2026 11:50 PM - 1 hour ago 4

The thought is to amended a caller consequence and beryllium that 4.5058(?)≤s(17) utilizing these weights:

But let’s first specify s(17). Quoting the aged article astir the topic

Let s(n) beryllium the broadside of the smallest quadrate into which we tin battalion n portion squares.

For n=16, the champion is evidently a 4x4 array, truthful s(16)=4.

For n=15, the 15 portion squares tin besides evidently beryllium enclosed successful a 4x4 quadrate truthful s(15)≤4. Proving that it’s the smaller quadrate is not evident astatine all. Anyway, Erich Friedman proved that successful 1999, truthful s(15)=4

For n=17, the evident enclosing quadrate is the 5x5, but successful 1998 John Bidwell recovered an illustration that shows that a quadrate of 4.6756… is enough, truthful s(17)≤4.6756… It’s a very absorbing statement of the squares, truthful it’s worthy visiting the postulation to spot it and the versions for different numbers.

On the different hand, Trevor Green proved successful 2000 that 4.4452…≤s(17), (more specifications later). So location was a immense spread 4.4452…≤s(17)≤4.6756…

A fewer weeks ago, Sam Burns pinch ChapGPT 5.6 Sol improved(?) the little bound. The caller bound is still not reviewed by the community. I took a look and it makes a batch of consciousness and I deliberation it’s correct, but I whitethorn beryllium missing a mini area lawsuit successful the impervious aliases the accompanying program, aliases I whitethorn beryllium missing a immense hole. I’ll adhd a mini (?) to the number conscionable successful case, but I’m rather optimistic and assured it’s correct truthful I’ll usage only a half font size. So the existent bound is 4.4452…≤4.4811(?)≤s(17)≤4.6756…

My main objection to Sam Burns is that it really deserved a bully graphic! So my first measurement will beryllium to adhd a bully schematic here. Also, making a fewer improvements to the program, I recovered a caller little bound that is 4.5058 So now we person 4.4452…≤4.4811(?)≤4.5058(?)≤s(17)≤4.6756…

My caller illustration and the modification of the codification are here, but the much method specifications astir uncovering the caller bound are portion of a second post.

Trevor Green’s bound

The thought of the aged impervious (19+40*sqrt(2))/17≅4.4452…≤s(17) of Trevor Green is to prime 16 very absorbing "unavoidable" points successful a quadrate of broadside 4.4452… and past he uses a batch of geometry to beryllium that immoderate portion quadrate must see astatine slightest 1 of them. So if we effort to fresh 17 portion squares there, astatine slightest 2 portion squares must stock 1 of the 16 absorbing points. The building chooses 16 points retired of a 4x6 grid.

I only recovered an image of the points in the aged article, but I couldn't find the analytical definition. Looking astatine the look for the broadside of the square, and utilizing a rule, and immoderate guessing, I deliberation that the quiet left/right separator is 0.5 and the quiet top/bottom separator is sqrt(2)-1/2≅0.9142… With these choices, the diagonal conception successful the original schematic has magnitude 1, which is simply a very useful number to make triangles that person vertices that are unavoidable points. (I’d beryllium gladsome to perceive a confirmation.)

It uses a 6x4 grid pinch an quiet separator of 0.9142… and 0.5000, and the full size of the grid is 2.6168… and 2.4452…

To comparison the building to the newer constructions, it’s amended to symmetrize it. In this symmetrized version each portion quadrate includes astatine slightest 4 points, but immoderate points are thicker, and they count arsenic double points (more specifications later).

Sam Burns’ bound

The thought to beryllium 4.4811(?)≤s(17) posted by Sam Burns using ChatGPT picks 268 somewhat absorbing points successful a quadrate of broadside 4.4811 The points person different weights, and the full weight is only 16.9476. After immoderate reductions, it’s only basal to trial a finite number of directions and they usage a programme successful Python to trial “all” the imaginable “almost-unit” (actually .9973) squares and verify that the sum of weight wrong each 1 of them is astatine slightest 1 (actually 1.0003). So if we effort to fresh 17 portion squares there, astatine slightest 2 portion squares must stock astatine slightest 1 of the 268 somewhat absorbing points. (More specifications successful the 2nd post.)

This method has mendacious negatives. If it verifies a solution past it’s surely correct, but if the programme fails location is simply a mini chance that it’s a mistake. This is good to guarantee the weight proves a little bound.

It’s not clear really the weights were selected. Comparing this solution to each the examples in the aged article, the 0.5 separator is excessively constrictive because astir examples usage ~1.0 aliases ~9.1 aliases thing for illustration that. The selections of weight work together pinch me, and each the weights successful the first/last row/column of the grid are zero. In my handwaving opinion, the second/penultimate row/columns should beryllium quiet too, but location is simply a non-zero weight successful (1, 11) of the grid and the symmetric images, I dream it is not basal successful a amended example. The third/penpenultimate row/column is rather full. It’s person to the separator than successful the aged examples, truthful it looks for illustration adding much points adjacent the separator whitethorn beryllium a bully thought to amended the bound.

I tie the images utilizing Racket pinch the Metapict package. The radius of each circle is calculated from the weight as

r = sqrt(weight^(1/gamma)) * scale

With gamma = 1.0 the area is proportional to the weight, but the mini weights are excessively mini successful the image. After immoderate tweaking, gamma=2.0 looks bully because the smaller weights are easier to see. The standard is not truthful mysterious, and I should person utilized pi location successful it, but scale=0.07 looks bully successful my machine. The circles are semi-transparent, truthful it’s imaginable to spot erstwhile they overlap if you ever summation the scale. The codification is astatine the bottom, and it divides the weight by 1.0003 that is the existent minimal sum.

New bound

My thought was to effort different combinations of the separator and soul grid size. As I said, it’s not clear really the weights were selected successful the illustration of Sam Burns. So for each fixed size, I decided to usage linear programming to find them.

Then I utilized a operation of brute unit hunt and luck to get the champion grid I could find. After that, I rounded the weight truthful they look bully and are bully fractions. (More specifications successful the 2nd post.)

After a batch of time, the champion I sewage is 4.5058(?)≤s(17). The caller solution uses 168 somewhat absorbing points successful a quadrate of broadside 4.5058 successful a 29x29 grid. They sum only 16.9166… Each portion quadrate includes astatine slightest a full weight of 1.There is an quiet separator of 0.77565 and the soul grid has a full broadside of 3.9545.

As I said, the weights are person to the separator than what I expected looking astatine the aged examples, adjacent to the second/penpenultimate row/column of the erstwhile one. It besides uses less weights, truthful I dream it’s easier to beryllium that it’s correct without a computer. I’d for illustration to make a non symmetric version, that whitethorn beryllium moreover better.

The programme published by Sam Burns assumes that the quiet separator is 0.5, truthful I had to modify it somewhat to let arbitrary borders pinch a adaptable M that is the double of the margin. The type pinch that modification, the caller sizes and the caller array of weight is astatine the bottom. Running that programme and making the evident changes to the explanation posted by Sam Burns proves(?) the caller bound.

Conclusion and Future Work

The distributions look rather discrete successful the corner, but it has immoderate unusual bars adjacent the center. It would beryllium bully to summation the grid size and return a look. Also, the constrictive quiet margins look to beryllium useful.
My hunt programme successful the 2nd article is excessively slow (like 1 hour), truthful I avoided changing the size of the grid. It whitethorn beryllium useful to research different grid sizes successful lawsuit location are immoderate absorbing coincidences.
Adding much digits takes only a fewer minutes, I didn't fuss because it looks for illustration refining the grid aliases utilizing much directions for the rotations would make bigger changes.
This consequence besides automatically improves the little bound of s(18), s(19) and s(20). But a much heavy hunt for those values should supply moreover amended bounds. I’ve seen excessively galore cases wherever the full sum of the weight is 18. There is thing absorbing astir 18.
I’d for illustration to find the non-symmetrical version. I person immoderate ideas to try, truthful cheque again successful a fewer days. A non-symmetrical type hopefully has for illustration 1/8 of the weight and hopefully shows the almost equilateral triangles and is easier to understand without a computer.

You whitethorn for illustration to publication the second post pinch specifications astir really I sewage the caller weights.

Program to verify the bound

from __future__ import annotations from bisect import bisect_left, bisect_right from fractions import Fraction arsenic F import numpy arsenic np # Original type posted by Sam Burns 2026 # Modified by Gustavo Massaccesi 2026 # Proposed nonstop lower-bound certificate for packing 17 portion squares successful a square. # # All geometric quantities and predicates are rational. NumPy is utilized only for # integer range-addition and cumulative sums; nary floating-point geometry is used. L = F(45058, 10000) # broadside of the square M = F(15513, 10000) # some quiet borders B = F(9973, 10000) T = F(207107, 500000) KMAX = 180 D = T / KMAX WEIGHT_SCALE = 576 # min weight NGRID = 29 LAST = NGRID - 1 # (i, j, w): each chopped D4 image of grid constituent (i,j) receives weight 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]]: measurement = (L - M) / LAST coord = [M / 2 + measurement * one for one successful range(NGRID)] by_index: dict[tuple[int, int], int] = {} for i, j, w successful CERT: for ij successful orbit(i, j): if ij successful by_index: raise ValueError(f"duplicate orbit duty astatine {ij}") by_index[ij] = w return [ (coord[i], coord[j], w) for (i, j), w successful sorted(by_index.items()) ] # Clip a convex logical polygon against U >= bound aliases 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 other p[0] <= bound prev = poly[-1] prev_in = inside(prev) for cur successful 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]]: # A B-square astatine predisposition (c,s) lies successful [0,L]^2 precisely erstwhile its # halfway lies successful [h,L-h]^2, pinch h=B(c+s)/2. # Transform that quadrate to the B-square's (U,V) frame. h = B * (c + s) / 2 lo, hullo = 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 successful corners_xy] def verify_orientation( c: F, s: F, atoms: list[tuple[F, F, int]], ) -> int: """Return the nonstop minimum integer people for 1 logical orientation.""" half = B / 2 dom = center_domain(c, s) u_dom_min = min(u for u, _ successful dom) u_dom_max = max(u for u, _ successful dom) v_dom_min = min(v for _, v successful dom) v_dom_max = max(v for _, v successful 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} # In halfway coordinates, atom rank is an axis-aligned rectangle. for x, y, w successful 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: one for i, x successful enumerate(ue)} vi = {x: one for i, x successful enumerate(ve)} # Exact integer 2D quality array. Scores are changeless successful each open # arena cell. NumPy performs only integer arithmetic here. diff = np.zeros((len(ue), len(ve)), dtype=np.int64) for u1, u2, v1, v2, w successful 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 champion = 10**18 for one successful range(nu): u0, u1 = ue[i], ue[i + 1] if u1 <= u_dom_min aliases 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 successful slab) vhi = max(v for _, v successful slab) if vhi <= vlo: continue # This whitethorn analyse a superset of feasible arena cells, which is # blimpish for a lower-bound verification. 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()) champion = min(best, row_min) if champion == 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 successful range(KMAX + 1): t = T * k / KMAX den = 1 + t * t c = (1 - t * t) / den s = 2 * t / den asseverate c * c + s * s == 1 out.append((c, s)) # The last adjacent brace brackets pi/4. asseverate out[-2][1] < out[-2][0] asseverate out[-1][1] >= out[-1][0] # If psi_k=2 arctan(t_k), half an adjacent angular spread is # arctan(t_{k+1})-arctan(t_k), whose tangent is # D/(1+t_k*t_{k+1}) <= D. Therefore each perspective successful [0,pi/4] # is wrong an correction epsilon < D of a nett direction. for k successful range(KMAX): t0 = T * k / KMAX t1 = T * (k + 1) / KMAX tan_half_gap = (t1 - t0) / (1 + t0 * t1) asseverate tan_half_gap <= D return out def main() -> None: atoms = build_atoms() full = sum(w for _, _, w successful atoms) print(f"atoms = {len(atoms)}") print( f"total_weight = {total}/{WEIGHT_SCALE}" f" = {total / WEIGHT_SCALE:.4f}" ) #assert len(atoms) == 268 #assert full == 169476 asseverate full < 17 * WEIGHT_SCALE nett = angle_net() # For an predisposition correction epsilon <= D, # cos(epsilon)+sin(epsilon) <= 1+epsilon <= 1+D. incorporate = B * (1 + D) print(f"angle_net_size = {len(net)}") print(f"b*(1+d) = {contain} = {float(contain):.12f} < 1") asseverate incorporate < 1 global_min = 10**18 argmin = -1 for k, (c, s) successful enumerate(net): m = verify_orientation(c, s, atoms) if m < global_min: global_min, argmin = m, k if k % 30 == 0 aliases k == KMAX: print( f"orientation {k:3d}/{KMAX}: " f"min={m}/{WEIGHT_SCALE}, " f"global={global_min}/{WEIGHT_SCALE}" ) print( f"minimum_score = {global_min}/{WEIGHT_SCALE}" f" = {global_min / WEIGHT_SCALE:.4f} astatine k={argmin}" ) asseverate global_min >= WEIGHT_SCALE print("CERTIFICATE CONDITIONS VERIFIED.") print(f"By the scaling argument: s(17) >= {L} = {L:.4f}.") if __name__ == "__main__": main()

Program to tie the images

#lang racket (require racket/list) (require metapict) {define-syntax-rule (for/append clauses assemblage ...) ; Todo: Add support for #:breack and #:final (append* (for/list clauses (begin assemblage ...)))} {define (mirror-x N atoms) (for/append ([a (in-list atoms)]) (match a [(list x y w) (list (list x y w) (list (- N 1 x) y w))]))} {define (mirror-y N atoms) (for/append ([a (in-list atoms)]) (match a [(list x y w) (list (list x y w) (list x (- N 1 y) w))]))} {define (mirror-d atoms) (for/append ([a (in-list atoms)]) (match a [(list x y w) (list (list x y w) (list y x w))]))} {define-values (L-Green atoms-Green) (let () ; Todo: Confirm these are the correct lenghts. (define grid-nx 6) (define grid-ny 4) (define border-size-y (- (sqrt 2) 1/2)) (define grid-size-y (/ (+ 12 (sqrt 8)) 17)) (define border-size-x 1) (define L (+ (* border-size-y 2) (* grid-size-y 3))) (define grid-size-x (/ (- L (* border-size-x 2)) 5)) {define atoms/int '(#;() (0 3 1) (1 3 1) (3 3 1) (5 3 1) (0 2 1) (2 2 1) (4 2 1) (5 2 1) (0 1 1) (1 1 1) (3 1 1) (5 1 1) (0 0 1) (2 0 1) (4 0 1) (5 0 1))} (define min-weight 1) {define atoms (for/list ([a (in-list atoms/int)]) (match a [(list x y w) (list (+ border-size-x (* grid-size-x x)) (+ border-size-y (* grid-size-y y)) (/ w min-weight))]))} (values L atoms))} {define-values (L-Green/S atoms-Green/S) (let () ; Todo: Confirm these are the correct lenghts. (define grid-nx 6) (define grid-ny 4) (define border-size-y (- (sqrt 2) 1/2)) (define grid-size-y (/ (+ 12 (sqrt 8)) 17)) (define border-size-x 1) (define L (+ (* border-size-y 2) (* grid-size-y (- grid-ny 1)))) (define grid-size-x (/ (- L (* border-size-x 2)) (- grid-nx 1))) ; It's easier to cipher the overlaps by hand (define atoms/gen '(#;() (0 1 2) (1 1 1) (2 1 1) (0 0 2) (1 0 1) (2 0 1))) (define min-weight 4) (define atoms/int (remove-duplicates (mirror-x grid-nx (mirror-y grid-ny atoms/gen)))) (define atoms/one-dir (for/list ([a (in-list atoms/int)]) (match a [(list x y w) (list (+ border-size-x (* grid-size-x x)) (+ border-size-y (* grid-size-y y)) (/ w min-weight))]))) (define atoms (mirror-d atoms/one-dir)) (values L atoms))} {define-values (L-Burns atoms-Burns) (let () (define grid-n 29) (define L 44811/10000) (define M 1) (define grid-size (/ (- L M) grid-n)) (define border-size (/ M 2)) (define min-weight 10003) {define atoms/gen '(#;() (1 11 107) (2 4 137) (2 9 214) (2 11 107) (2 12 137) (3 4 3884) (3 7 214) (3 8 913) (3 9 214) (3 10 214) (3 11 1234) (3 12 2189) (3 14 384) (4 4 1961) (4 7 520) (4 8 214) (4 9 1413) (4 10 1234) (4 11 1083) (4 13 137) (4 14 292) (7 11 529) (7 12 33) (8 10 906) (8 11 384) (8 12 351) (9 9 340) (9 10 180) (9 11 204) (9 12 549) (10 12 879) (10 13 201) (10 14 378) (11 11 396) (11 12 622) (11 13 204) (11 14 204))} (define atoms/int (remove-duplicates (mirror-x grid-n (mirror-y grid-n (mirror-d atoms/gen))))) (define atoms (for/list ([a (in-list atoms/int)]) (match a [(list x y w) (list (+ border-size (* grid-size x)) (+ border-size (* grid-size y)) (/ w min-weight))]))) (values L atoms))} {define-values (L-Massaccesi atoms-Massaccesi) (let () (define grid-n 29) (define L 45058/10000) (define M 15513/10000) (define grid-size (/ (- L M) grid-n)) (define border-size (/ M 2)) (define min-weight 576) {define atoms/gen '(#;() (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))} (define atoms/int (remove-duplicates (mirror-x grid-n (mirror-y grid-n (mirror-d atoms/gen))))) (define atoms (for/list ([a (in-list atoms/int)]) (match a [(list x y w) (list (+ border-size (* grid-size x)) (+ border-size (* grid-size y)) (/ w min-weight))]))) (values L atoms))} {define (draw-example L atoms #:gamma [gamma 2.0] #:scale [scale 0.07]) [with-window (window -.1 (+ L .1) -.1 (+ L .1)) (define big-fill-color "whitesmoke") (define big-border-color "black") (define dots-color (change-alpha "darkred" 0.75)) (define big-square (curve (pt 0 0) -- (pt 0 L) -- (pt L L) -- (pt L 0) -- cycle)) (draw (color big-fill-color (fill big-square)) (penscale .1 (color big-border-color (draw big-square))) (draw* (for/list ([a (in-list atoms)]) (match a [(list x y w) (define s (* (sqrt (expt w (/ 1. gamma))) scale)) (penstyle 'transparent (color dots-color (filldraw (circle (pt x y) s))))])))) ]} (scale 4 (draw-example L-Green atoms-Green #:gamma 2.0 #:scale .07)) (scale 4 (draw-example L-Green/S atoms-Green/S #:gamma 2.0 #:scale .07)) (scale 4 (draw-example L-Burns atoms-Burns #:gamma 2.0 #:scale .07)) (scale 4 (draw-example L-Massaccesi atoms-Massaccesi #:gamma 2.0 #:scale .07))