Fractal đã treo trên tường tôi suốt 12 năm

 (chriskw.xyz)
2 điểm bởi GN⁺ 2025-05-23 | 1 bình luận | Chia sẻ qua WhatsApp
  • Sau khi để mẫu sao chép hình vuông vẽ trên giấy kẻ ô hồi cấp hai treo trên tường suốt 12 năm, tác giả phân tích nó như một fractal tên là wallflower, liên hệ tới L-System, đại số tuyến tính, hệ thống số và khái quát hóa lên chiều cao hơn
  • Bắt đầu từ một hình vuông, sao chép hình hiện tại sang trên, dưới, trái, phải; ở bước tiếp theo sao chép theo các hướng xoay khoảng 27 độ, quy trình này tạo ra một fractal lấp đầy mặt phẳng
  • Quy tắc L-System đơn giản R → RLR, L → RLL tạo ra đường bao tương tự nhưng không phải cùng một hình; dạng phổ biến hơn đã được ghi nhận dưới các tên Quadratic von Koch island, Quadratic Flake, Minkowski Sausage...
  • wallflower có thể được diễn giải như một hệ thống số dựa trên ma trận, dùng ma trận (M=\begin{bmatrix}-2&1\1&2\end{bmatrix}) làm cơ số và dùng vector hướng làm chữ số; (\det(M)=-5) làm đảo hướng ở mỗi lần lặp
  • Khái quát hóa lên 3D trở nên gượng do vấn đề đối xứng và chồng lấn; trong 4D có thể tạo orthotopeflower bằng ma trận thỏa điều kiện, nhưng với cùng ràng buộc có vẻ chỉ khả thi ở 1D, 2D và 4D

Khởi đầu của fractal treo trên tường

  • Hồi cấp hai, tôi đã vẽ nguệch ngoạc trên giấy kẻ ô một mẫu lặp bằng cách ghép và sao chép các hình vuông, rồi dán nó lên tường để sau này phân tích
  • Vì cấu trúc xòe ra như cánh hoa và câu chuyện nó ở trên tường rất lâu, tôi gọi fractal này là wallflower
  • Quy trình vẽ ban đầu như sau
    • Bắt đầu từ một hình vuông
    • Đặt 4 bản sao của trạng thái hiện tại ở bên trái, bên phải, bên trên và bên dưới
    • Tiếp theo, đặt 4 bản sao của trạng thái hiện tại ở bốn hướng tương tự nhưng nghiêng khoảng 27 độ theo chiều kim đồng hồ
    • Lặp luân phiên hai cách bố trí cho đến khi giấy kẻ ô được lấp đầy
  • Quy trình này, nếu lặp lại, có thể phủ một vùng bất kỳ của mặt phẳng như Gosper Curve, và mỗi trạng thái trung gian cũng có thể lát kín mặt phẳng

Gần giống L-System nhưng đường bao khác

  • Khoảng một năm trước, tôi thấy đường bao này có thể được tạo bằng L-System
  • Quy tắc dùng chỉ gồm phép rẽ phải 90 độ (R) và rẽ trái (L)
    • Chuỗi khởi đầu là (RRRR)
    • Ở mỗi lần lặp, thay (R \rightarrow RLR), (L \rightarrow RLL)
  • Vài bước đầu trông như có cùng đường bao với wallflower, nhưng khi làm hoạt ảnh, tôi xác nhận rằng hai cách bắt đầu lệch nhau từ lần lặp thứ 4
  • Khác biệt đến từ cách đặt các bản sao
    • Cách “drag and drop” đặt trực tiếp bản sao của lần lặp thứ 3 lên trên, dưới, trái, phải so với tâm
    • Cách L-System đặt các bản sao theo hướng chéo
  • Hình do L-System tạo ra đã được ghi nhận ở nhiều nơi
  • Biến thể drag and drop từng treo trên tường thì không tìm thấy hình tương tự qua Google Images và tra cứu Wikipedia
  • Tôi tìm được quy tắc phù hợp với wallflower là (L \rightarrow RLR), (R \rightarrow LLR), nhưng quy tắc này tạo hiệu ứng đảo ngược hướng vẽ đường bao ở mỗi bước

Cách đếm fractal

  • Vì wallflower lớn dần từ gốc tọa độ ra ngoài, có thể xem nó như một cách ánh xạ số tự nhiên với tọa độ lưới
  • Đặt hình vuông trung tâm là 0, rồi đánh số 4 hình vuông xung quanh được thêm ở lần lặp đầu tiên theo chiều kim đồng hồ là 1, 2, 3, 4
  • Ở lần lặp tiếp theo cũng có thể quét từ trên xuống dưới, từ trái sang phải để đánh số, nhưng cách này không khớp tốt với cấu trúc đệ quy
  • Tận dụng việc mỗi cánh hoa là bản sao của lần lặp trước, ta có thể tái sử dụng cách đánh số từ trung tâm ra ngoài cả bên trong từng cánh hoa lẫn giữa các cánh hoa
  • Với cách đánh số này, các bội số của 5, (5n+1), bội số của 25... tạo thành các mẫu lưới nghiêng
  • Lý do là số hình vuông ở mỗi lần lặp tăng theo (1, 5, 25, 125, ...)
    • Mỗi lần lặp thêm 4 bản sao vào 1 trạng thái trước đó, tổng cộng thành gấp 5 lần
    • Vì vậy lũy thừa của 5 và biểu diễn cơ số 5 rất khớp với cấu trúc này

Hệ thống số dùng ma trận làm cơ số

  • Nếu phân rã một số như các hàng trong hệ ngũ phân, ta có thể tìm vị trí trên lưới fractal bằng cách cộng các vector tương ứng với từng hàng
  • Ví dụ, coi 231 là (200 + 30 + 1), rồi cộng các vector vị trí tương ứng để thu được vị trí của 231
  • Giá trị một chữ số được định nghĩa bằng vector hướng
    • (\vec{0}=(0,0))
    • (\vec{1}=(1,0))
    • (\vec{2}=(0,1))
    • (\vec{3}=(-1,0))
    • (\vec{4}=(0,-1))
  • Các hàng dạng (10^n) ban đầu được biểu diễn bằng công thức điều kiện tách theo chẵn/lẻ, nhưng có thể tính không cần điều kiện bằng cách lặp áp dụng một ma trận duy nhất
  • Ma trận được dùng như sau

[ M=\begin{bmatrix} -2 & 1 \ 1 & 2 \end{bmatrix} ]

  • Ma trận này có (M^2=5I), nên cứ mỗi hai bước thì kích thước được căn chỉnh tăng gấp 5 lần
  • Do đó có thể biểu diễn như sau

[ \overrightarrow{(10^n)}=M^n\vec{1} ]

  • Cấu trúc này có thể được xem như một hệ thống số dùng cơ số ma trận và chữ số vector, thay cho hệ cơ số thông thường dùng cơ số vô hướng và chữ số vô hướng

Định thức phân tách hai fractal

  • Định thức của (M) là (\det(M)=-5), và định thức âm làm hướng của không gian bị đảo ở mỗi lần lặp
  • Vì sự đảo hướng này, so với cách đánh số ban đầu, vị trí của các giá trị như 20 và 40 trông như bị đổi chỗ
  • Nếu muốn tránh đảo hướng, có thể chọn ma trận có định thức dương

[ M'=\begin{bmatrix} 2 & 1 \ -1 & 2 \end{bmatrix} ]

[ \det(M')=5 ]

  • (M') không đảo hướng mà tiếp tục xoay các vector chữ số theo chiều kim đồng hồ; dùng ma trận này làm cơ số sẽ tái tạo phiên bản L-System đã nói ở trên
  • Khác biệt giữa hai fractal như sau
    • wallflower đến từ (M) với (\det(M)=-5)
    • họ quadratic flake phổ biến hơn đến từ (M') với (\det(M')=5)
  • Trị tuyệt đối 5 của định thức khớp với cấu trúc fractal tăng kích thước gấp 5 lần ở mỗi lần lặp
    • Nếu định thức lớn hơn, các bản sao sẽ lớn quá nhanh và tạo khoảng trống
    • Nếu định thức nhỏ hơn, các bản sao sẽ lớn quá chậm và các lần lặp sẽ chồng lên nhau
  • Góc khoảng 27 độ liên quan đến vector (\langle1,2\rangle), xuất phát từ điều kiện tọa độ nguyên, định thức (\pm5), và độ dài vector (\sqrt5)
    • Góc của vector này là (\arctan(2/1)\approx63.43^\circ)
    • So với trục y thì lệch khoảng 27 độ

Quy tắc cộng và nhớ

  • Phép cộng vector khớp tốt với các hàng đã khai triển, nhưng hoạt động khác phép cộng số thông thường, chẳng hạn (\vec{2}+\vec{2}\neq\vec{4})
  • Từ 1 đến 4 nên được xem là các hướng trên, phải, dưới, trái hơn là các số thực sự
  • Các hướng đối nhau triệt tiêu lẫn nhau
    • (\vec{1}+\vec{3}=\vec{0})
    • (\vec{2}+\vec{4}=\vec{0})
  • Nếu lập bảng các tổ hợp vector đơn vị, một số kết quả cộng sẽ thành giá trị hai chữ số
  • Vì vậy khi cộng các số lớn, cần xử lý nhớ giống phép cộng dài thông thường
  • Ví dụ, khi tính (\vec{22}+\vec{1}), do quy tắc (\vec{2}+\vec{1}=\vec{13}), kết quả là 133
  • Tôi không chứng minh hệ cộng này hoạt động tổng quát, mà để lại cho độc giả kiểm chứng

Các hệ thống số và nghiên cứu liên quan

  • Hệ thống số của fractal wallflower liên hệ với những hệ cơ số khác không chỉ dùng số tự nhiên làm chữ số
  • Balanced Ternary dùng (-1,0,1) làm chữ số và dùng 3 làm cơ số; wallflower có thể được xem như một tương tự hai chiều của nó, bổ sung các chữ số theo hướng dương và âm của trục y
  • generalized balanced ternary được khái quát hóa lên mọi chiều bằng lưới permutohedron, và trong 2D trở thành lưới lục giác
  • Quater-imaginary Base là hệ dùng (2i) làm cơ số và 0, 1, 2, 3 làm chữ số
  • (M') có thể được xem như cơ số tương ứng với số phức (2+i), và Balanced base 2+i (and some gratuitous fractals) của Timothy James McKenzie Makarios đề cập đến khái niệm này
  • Tôi tìm được các tài liệu liên quan sau
    • Project BinSys: dự án tìm cơ số ma trận có định thức 2
    • Replicating Tesselations của Andrew Vince: xử lý fractal, lát mặt phẳng, đại số tuyến tính và hệ thống số một cách chặt chẽ hơn, đồng thời mở rộng vượt ra ngoài (\mathbb{Z}^2) sang các lưới tổng quát

Mở rộng lên 3D và 4D

  • Trong 3D, tôi nghĩ đến cấu trúc “3D plus”, bắt đầu từ một khối lập phương rồi sao chép theo sáu hướng
  • Các điều kiện mong muốn cho ma trận 3x3 như sau
    • Mọi phần tử phải là số nguyên
    • Mỗi vector cột phải có khoảng cách Hamming bằng 3 so với gốc tọa độ
    • Vì mỗi lần lặp thêm 6 bản sao, kích thước phải tăng gấp 7 lần, và định thức phải là (\pm7)
  • Tôi tìm được một ma trận 3x3 thỏa điều kiện, nhưng kết quả trực quan hóa trở thành một hình như bị ép bẹt, đồng thời các lần lặp trước bị lộ ra
  • Nếu thêm hai 3D plus nữa thì có thể lấp các phần trống, và 8 điểm trung tâm được sắp như các đỉnh của một khối lập phương bị vặn
  • Để có bố trí đối xứng hơn, điều kiện mỗi cột trực giao với nhau và có cùng độ dài có thể là đủ, nhưng trong 3D điều này dường như bất khả thi vì không khớp với điều kiện tọa độ nguyên
  • Trong 4D thì các điều kiện khớp với nhau
    • Chỉ cần tổng bình phương các thành phần của mỗi vector cột bằng 3
    • Có thể đặt 3 trong 4 thành phần là (\pm1), và một thành phần là 0
  • Tôi dựng fractal 4D bằng ma trận 4x4 sau

[ \begin{bmatrix} 0 & -1 & -1 & -1 \ 1 & 0 & -1 & 1 \ 1 & 1 & 0 & -1 \ 1 & -1 & 1 & 0 \end{bmatrix} ]

  • Fractal 4D này được gọi là orthotopeflower
  • Trực quan hóa 4D được xử lý bằng cách xem các lát cắt 3D với giá trị (w) cố định, hoặc biểu diễn cửa sổ bốn chiều bằng cách đặt các lưới 7x7 bên trong một lưới 7x7
  • Trong cửa sổ xem 31x31x31x31, nó trông như mở rộng ra ngoài mà không bị ép quá mức như trong 3D

Chiều cao hơn và cú đảo cuối cùng

  • Nếu mở rộng cùng các ràng buộc lên chiều cao hơn, có vẻ các chiều thỏa điều kiện chỉ là 1D, 2D và 4D
    • 1D là balanced ternary
    • 2D là wallflower hoặc quadratic flake
    • 4D là orthotopeflower
  • Ma trận được chọn trong 4D mã hóa quaternion (i+j+k), từ đó có thể nghĩ đến một balanced nonary quaternion base với cơ số (i+j+k) và các chữ số (0,\pm1,\pm i,\pm j,\pm k)
  • Tôi không chắc hệ quaternion này có thực sự hoạt động hay không, nên để lại cho bản thân trong tương lai khi biết nhiều toán hơn
  • Sau burnout, nỗ lực khơi lại hứng thú với toán học và lập trình đã biến một nét vẽ nguệch ngoạc cũ thành hành trình khám phá nối fractal, hệ thống số, đại số tuyến tính và các chiều cao hơn
  • Cú đảo cuối cùng là các hình trực quan trong bài không khớp với fractal thật trên tường ở thumbnail
    • Lần lặp thứ 4 của hình thật trên tường được sao chép theo hướng ngược lại với khoảng 27 độ
    • Khi đó tôi nghĩ rằng nếu cứ nghiêng cùng một hướng thì nó sẽ lệch khỏi trục nên đã cố hiệu chỉnh, nhưng cấu trúc của (M) vốn đã tự hiệu chỉnh ở mỗi bước
    • Kết thúc bằng việc Donald Knuth cũng từng rẽ wrong turn khi dán fractal lên tường

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-05-23
Ý kiến trên Hacker News

  • Một bài viết sâu sắc và được đầu tư kỹ lưỡng, phần trực quan hóa 3D đặc biệt hay
    Nó làm tôi nhớ đến thứ từng làm khi mày mò decimation đệ quy để tạo hiệu ứng giống fractal từ ảnh bất kỳ
    Có thể thử trực tiếp ở đây: https://jsfiddle.net/nicobrenner/a1t869qf/
    Nhấn Blursort 2x2 vài lần để tạo frame rồi nhấn Animate là được. Cũng có thể copy/paste ảnh, và mọi thứ chạy hoàn toàn trong trình duyệt, không cần backend. Không khuyến nghị dùng trên mobile

    • Tò mò liệu cái này có hoạt động trong 3D không

  • Tôi bị cuốn vào chuyện này và có vẻ đã tạo ra một dạng lấp đầy “wallflower” bằng L-system
    https://onlinetools.com/math/l-system-generator?draw=AB&skip...
    Nghĩ lại thì cái này có lẽ tạo ra một fractal khác, nhưng tôi không chắc

  • Tôi tưởng đây sẽ là bài đọc nhẹ nhàng, nhưng vì phải làm việc nên chỉ có thể đọc lướt một phần
    Tôi định quay lại sau để vọc thử đủ thứ; bài viết thật sự được làm rất tốt

  • Bài viết sâu và nặng hơn tôi tưởng rất nhiều, cảm nhận được sự tận tâm
    Muốn hỏi tác giả: bây giờ anh/chị sẽ khuyên treo gì trên tường phòng của con?

    • Tôi hoàn toàn không phải chuyên gia nuôi dạy trẻ, nhưng tôi nghĩ bất cứ thứ gì liên quan đến điều khiến đứa trẻ cảm thấy đam mê hoặc kinh ngạc vào thời điểm đó đều tốt
      Tôi có chèn nhẹ một đoạn về burnout ở cuối bài. Với tôi, gốc rễ vấn đề là đã đánh mất sự mê hoặc và tò mò từng có với toán học và lập trình; khi viết bài này, tôi đã có thể chạm lại vào cảm giác kinh ngạc trẻ thơ mà trước đây từng dễ dàng cảm nhận

  • Tôi đã kiểm tra phép tính số học với hai số có hai chữ số, và nó thực sự hoạt động
    Tôi từng đoán 41+14 sẽ ra 12. Vì cộng hai ô bên phải và hai ô phía trên thì vẫn là hai ô bên phải, hai ô phía trên
    Trong phép cộng dài bên dưới, = được dùng khi cho thấy sự tương đương, tức là sắp xếp lại hạng tử (1+2=2+1), phân tách số (41=40+1), cộng một chữ số (1+4=22); -> được dùng khi thuật toán đưa ra chữ số, còn < dùng khi chuyển sang cột tiếp theo
    41+14 = (40+1)+(10+4) = 40 + 10 + (1+4) = 40 + 10 + 22 -> 1s digit = 2 < 4 + 1 + 2 = 22 + 2 = 20 + 2 + 2 = 20 + 41 -> 10s digit = 1 < 2 + 4 = 0 -> done == 12
    Trong bài có hai hệ cơ số khác nhau: một hệ có 10, 20, 30, 40 theo chiều kim đồng hồ, hệ kia ngược chiều kim đồng hồ. Cả hai đều có 1, 2, 3, 4 theo chiều kim đồng hồ. Phép cộng trên dựa trên hệ thứ hai dùng trong bảng cộng, tức hệ mà các hàng chục đi ngược chiều kim đồng hồ
    Nó cũng hoạt động trong hệ còn lại. 14+21 phải ra 12
    14+21 =10+20+42 ->2 <1+2+4 =13+4 =10+3+4 =10+31 ->1 <1+3 =0 ==12

  • Tôi tò mò anh/chị đã nghĩ ra hệ đánh số “middle out” như thế nào
    Khi tự giải toán, tôi hiếm khi nảy ra được những ý tưởng kiểu được truyền cảm hứng như vậy

    • Trong bài, trình tự có vẻ hơi khác, nhưng rốt cuộc điểm xuất phát là khoảnh khắc nhận ra cách fractal tăng trưởng gấp 5 lần, hệ số cơ số 5, và “xoắn ốc” nói trong bài có thể ăn khớp với nhau
      Tôi cũng đã nghĩ rất nhiều về cách vẽ fractal bằng chương trình, và cách tự nhiên là bắt đầu từ giữa rồi mở rộng ra ngoài
      Có một giai thoại rằng Richard Feynman luôn để khoảng hơn chục vấn đề ngẫu nhiên ở phía sau tâm trí, rồi mỗi khi thấy một mối liên hệ thì tiến thêm một chút; đến khi cuối cùng giải được một vấn đề, mọi người tưởng ông đã nghĩ ra ngay tại chỗ như có phép thuật. Lần này cũng hơi giống vậy, nhưng tôi còn xa mới ở tầm đó, và không phải hơn chục vấn đề mà chỉ là cố gắng làm được như thế với đúng một vấn đề

  • Ở nơi tôi từng làm việc, chúng tôi đã treo nó dưới dạng bản in cỡ lớn trên tường
    https://raw.githubusercontent.com/cies/haskell-fractal/refs/... [17MB, xin lỗi vì là Github]
    Cũng có mã Haskell dùng để tạo nó: https://github.com/cies/haskell-fractal
    Quá trình nghĩ ra hàm sharpen đặc biệt thú vị. Để khớp đường cong, tôi đã dùng một công cụ nay không còn nữa: https://github.com/cies/haskell-fractal/blob/master/fractal....
    Đó là một dự án nhỏ thú vị

  • Tôi đồng cảm với đoạn “quyết định ủy thác cho bản thân tương lai biết nhiều toán hơn”
    Danh sách những vấn đề tôi cần giải nhưng chưa giải được vì thiếu bản đồ và kết nối Internet cũng ảnh hưởng lớn đến việc tôi chọn học bằng gì. Phần lớn là các vấn đề đại số tuyến tính

  • Có vẻ có lỗi đánh máy trong công thức mẫu. Ngay sau câu “Looking closely you might pick up on the pattern”, biểu thức nên là 5**(n/2) chứ không phải 5**n, và 5**((n-1)/2) chứ không phải 5**(n-1)
    \overrightarrow{10*4} là [0, 25], nhưng theo công thức ban đầu thì ra [0, 625]
    Ngoài ra, về sai sót của Knuth, trong bình luận YouTube có nói rằng fractal của ông thực ra đúng, chỉ là ông nhầm điểm bắt đầu và điểm kết thúc. Nói lỏng lẻo thì fractal đó đối xứng theo phép quay ở giữa, và chính phép quay đó là thứ Knuth cho là sai. Dù sao thì ông vẫn đã mắc một lỗi liên quan đến fractal, nên kết luận vẫn giữ nguyên

    • Tìm hay lắm, tôi đã sửa công thức