# Is every integer representable as the sum of four Fibonacci squares?

Lagrange's Four Square Theorem. Every positive integer $$N$$ can be written as the sum of four squares, i.e.,

$$N = a^2 + b^2 + c^2 + d^2.$$

Zeckendorf's Theorem. Every integer has a unique representation where it can be written as the sum of non-consecutive Fibonacci numbers. i.e.,

$$N = \sum_i F_{c_i}, c_i \in \mathbb{Z}, c_i \ge 2, c_{i+1} \gt c_i + 1,$$

where $$F_k$$ is the Fibonacci sequence generated by the recurrence equation $$F_{n+2} = F_{n+1} + F_n$$ with $$F_0 = 0, F_1 = 1$$.

Question: Is every positive integer also representable as the sum of four Fibonacci squares?

\begin{align} 0 &= F_0^2 \\ 1 &= F_1^2 \\ 2 &= F_1^2 + F_1^2 \\ 3 &= F_1^2 + F_1^2 + F_1^2 \\ 4 &= F_3^2 \\ 5 &= F_3^2 + F_1^2 \\ 6 &= F_3^2 + F_1^2 + F_1^2 \\ 7 &= F_3^2 + F_1^2 + F_1^2 + F_1^2 \\ 8 &= F_3^2 + F_3^2 \\ 9 &= F_4^2 \\ 10 &= F_4^2 + F_1^2 \\ 11 &= F_4^2 + F_1^2 + F_1^2 \\ 12 &= F_4^2 + F_1^2 + F_1^2 + F_1^2 \\ 13 &= F_4^2 + F_3^2 \\ 14 &= F_4^2 + F_3^2 + F_1^2 \\ 15 &= F_4^2 + F_3^2 + F_1^2 + F_1^2 \\ 16 &= F_3^2 + F_3^2 + F_3^2 + F_3^2 \end{align}

Note that in the sums above, if we have fewer than $$4$$ squares, we can always add $$F_0^2 = 0^2$$ to make it a four square representation.

The sum of four Fibonacci squares representation, if it exists, is not necessarily unique for an integer. e.g.,

\begin{align} 4 &= F_1^2 + F_1^2 + F_1^2 + F_1^2 \\ &= F_3^2 + F_0^2 + F_0^2 + F_0^2 \end{align}

If $$N$$ is big, there are only about $$\ln N$$ Fibonacci squares below $$N$$. There are then at most $$(\ln N)^4$$ different sums below $$N$$. That count eventually grows more slowly than $$N$$, so gaps will appear.
I don't know when the first gap will be

• Thank you. I've accepted @mihaild's answer and upvoted yours. Your explanation is concise and logical.
– vvg
Commented Jul 19, 2023 at 9:53
• It follows from this that for every $k$, there are integers that are not representable as a sum of $k$ Fibonacci squares. Commented Jul 20, 2023 at 20:45
• And more general, for any non-periodic linear recurrent sequence, any set of $n$ functions that grow at least linearly, and number $k$, there are numbers that are not sum of at most $k$ terms where each term is function of some term of sequence. Commented Jul 21, 2023 at 13:39

Bruteforce gives that first gap is $$24$$: the only Fibonacci squares less than $$24$$ are $$0, 1, 4, 9$$. We need at least two nines (otherwise sum is at most $$9 + 3 \cdot 4 = 21$$), so now we have to represent $$6$$ as sum of two numbers from $$0,1,4$$. But such sum is either $$8$$, or at most $$5$$. Thus $$24$$ isn't sum of $$4$$ Fibonacci squares.

It is not hard to find representation for numbers from 17 to 23.

(but of course Empy2's argument is much more elegant then this)

• Your answer is better (more elegant) I think. Finding such a small counter example is a more convincing proof than using function growth rate (for example, the other might need some more proof to show ln^4 N grows more slowly than N to be completely rigorous, while yours is already complete). Commented Jul 20, 2023 at 5:03
• This shows the two types of proofs: One is fast and rigorous, but doesn't betray much insight; another is slow and perhaps verbose/unclear, but has much more to learn from. Commented Jul 20, 2023 at 12:36
• @justhalf: on the other hand, it is straightforward to see how Empy2's answer could be extended to the more general question "does there exist a $k$ such that every positive integer can be expressed by $k$ Fibonacci squares" Commented Jul 20, 2023 at 14:02

By computer search, the possible representations for integers up to 50 are (note, $$F_2=1=F_1$$ so we only give representations using $$F_1$$ for brevity) \begin{align} 0 &= F_0^2& 1 &= F_{1}^2\\ 2 &= F_{1}^2+F_{1}^2& 3 &= F_{1}^2+F_{1}^2+F_{1}^2\\ 4 &= F_{3}^2& 4 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{1}^2\\ 5 &= F_{1}^2+F_{3}^2& 6 &= F_{1}^2+F_{1}^2+F_{3}^2\\ 7 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{3}^2& 8 &= F_{3}^2+F_{3}^2\\ 9 &= F_{4}^2& 9 &= F_{1}^2+F_{3}^2+F_{3}^2\\ 10 &= F_{1}^2+F_{4}^2& 10 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{3}^2\\ 11 &= F_{1}^2+F_{1}^2+F_{4}^2& 12 &= F_{3}^2+F_{3}^2+F_{3}^2\\ 12 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{4}^2& 13 &= F_{3}^2+F_{4}^2\\ 13 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{3}^2& 14 &= F_{1}^2+F_{3}^2+F_{4}^2\\ 15 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{4}^2& 16 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{3}^2\\ 17 &= F_{3}^2+F_{3}^2+F_{4}^2& 18 &= F_{4}^2+F_{4}^2\\ 18 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{4}^2& 19 &= F_{1}^2+F_{4}^2+F_{4}^2\\ 20 &= F_{1}^2+F_{1}^2+F_{4}^2+F_{4}^2& 21 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{4}^2\\ 22 &= F_{3}^2+F_{4}^2+F_{4}^2& 23 &= F_{1}^2+F_{3}^2+F_{4}^2+F_{4}^2\\ 25 &= F_{5}^2& 26 &= F_{1}^2+F_{5}^2\\ 26 &= F_{3}^2+F_{3}^2+F_{4}^2+F_{4}^2& 27 &= F_{1}^2+F_{1}^2+F_{5}^2\\ 27 &= F_{4}^2+F_{4}^2+F_{4}^2& 28 &= F_{1}^2+F_{1}^2+F_{1}^2+F_{5}^2\\ 28 &= F_{1}^2+F_{4}^2+F_{4}^2+F_{4}^2& 29 &= F_{3}^2+F_{5}^2\\ 30 &= F_{1}^2+F_{3}^2+F_{5}^2& 31 &= F_{1}^2+F_{1}^2+F_{3}^2+F_{5}^2\\ 31 &= F_{3}^2+F_{4}^2+F_{4}^2+F_{4}^2& 33 &= F_{3}^2+F_{3}^2+F_{5}^2\\ 34 &= F_{4}^2+F_{5}^2& 34 &= F_{1}^2+F_{3}^2+F_{3}^2+F_{5}^2\\ 35 &= F_{1}^2+F_{4}^2+F_{5}^2& 36 &= F_{1}^2+F_{1}^2+F_{4}^2+F_{5}^2\\ 36 &= F_{4}^2+F_{4}^2+F_{4}^2+F_{4}^2& 37 &= F_{3}^2+F_{3}^2+F_{3}^2+F_{5}^2\\ 38 &= F_{3}^2+F_{4}^2+F_{5}^2& 39 &= F_{1}^2+F_{3}^2+F_{4}^2+F_{5}^2\\ 42 &= F_{3}^2+F_{3}^2+F_{4}^2+F_{5}^2& 43 &= F_{4}^2+F_{4}^2+F_{5}^2\\ 44 &= F_{1}^2+F_{4}^2+F_{4}^2+F_{5}^2& 47 &= F_{3}^2+F_{4}^2+F_{4}^2+F_{5}^2\\ 50 &= F_{5}^2+F_{5}^2.& \end{align}

The integers up to $$1000$$ without such a representation are

24, 32, 40, 41, 45, 46, 48, 49, 53, 56, 57, 61, 62, 71, 80, 85, 87, 88, 92, 95, 96, 101, 103, 104, 105, 106, 108, 109, 110, 111, 112, 113, 116, 117, 119, 120, 121, 122, 124, 125, 126, 127, 131, 134, 135, 140, 142, 143, 144, 145, 147, 148, 149, 150, 151, 152, 155, 156, 158, 159, 160, 161, 163, 164, 165, 166, 167, 168, 176, 184, 185, 189, 190, 197, 200, 205, 206, 208, 209, 210, 211, 213, 214, 215, 216, 218, 221, 222, 224, 225, 226, 227, 229, 230, 231, 232, 236, 239, 240, 245, 247, 248, 249, 250, 252, 253, 254, 255, 257, 260, 261, 263, 264, 265, 266, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 299, 300, 302, 303, 304, 305, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 341, 344, 345, 349, 350, 352, 353, 354, 355, 357, 358, 359, 360, 362, 365, 366, 368, 369, 370, 371, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 404, 405, 407, 408, 409, 410, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 448, 456, 457, 461, 462, 464, 465, 469, 472, 473, 477, 478, 480, 481, 482, 483, 485, 486, 487, 488, 489, 490, 493, 494, 496, 497, 498, 499, 501, 502, 503, 504, 512, 517, 519, 520, 521, 522, 524, 525, 526, 527, 528, 529, 533, 535, 536, 537, 538, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 572, 574, 575, 576, 577, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 613, 616, 617, 621, 622, 624, 625, 626, 627, 629, 630, 631, 632, 634, 637, 638, 640, 641, 642, 643, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 677, 679, 680, 681, 682, 684, 685, 686,687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 781, 782, 784, 785, 786, 787, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 844, 845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875, 876, 877, 878, 879, 880, 881, 885, 888, 889, 893, 894, 896, 897, 898, 899, 901, 902, 903, 904, 905, 906, 909, 910, 912, 913, 914, 915, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 933, 934, 935, 936, 937, 938, 939, 940, 941, 942, 943, 944, 945, 949, 951, 952, 953, 954, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000

The list of integers up to $$1000$$ with this representation is shorter:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 42, 43, 44, 47, 50, 51, 52, 54, 55, 58, 59, 60, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 86, 89, 90, 91, 93, 94, 97, 98, 99, 100, 102, 107, 114, 115, 118, 123, 128, 129, 130, 132, 133, 136, 137, 138, 139, 141, 146, 153, 154, 157, 162, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 186, 187, 188, 191, 192, 193, 194, 195, 196, 198, 199, 201, 202, 203, 204, 207, 212, 217, 219, 220, 223, 228, 233, 234, 235, 237, 238, 241, 242, 243, 244, 246, 251, 256, 258, 259, 262, 267, 283, 297, 298, 301, 306, 322, 338, 339, 340, 342, 343, 346, 347, 348, 351, 356, 361, 363, 364, 367, 372, 388, 402, 403, 406, 411, 427, 441, 442, 443, 444, 445, 446, 447, 449, 450, 451, 452, 453, 454, 455, 458, 459, 460, 463, 466, 467, 468, 470, 471, 474, 475, 476, 479, 484, 491, 492, 495, 500, 505, 506, 507, 508, 509, 510, 511, 513, 514, 515, 516, 518, 523, 530, 531, 532, 534, 539, 555, 569, 570, 571, 573, 578, 594, 610, 611, 612, 614, 615, 618, 619, 620, 623, 628, 633, 635, 636, 639, 644, 660, 674, 675, 676, 678, 683, 699, 738, 779, 780, 783, 788, 804, 843, 882, 883, 884, 886, 887, 890, 891, 892, 895, 900, 907, 908, 911, 916, 932, 946, 947, 948, 950, 955, 971

This was created by the Scala 3 code below that can probably be improved; it runs in under a second on my computer if you set max = 10000. Click here to run it online in Scastie.

val max = 1000

def fibFrom(n: Int, m: Int): LazyList[Int] =
n #:: m #:: fibFrom(n + m, n + 2 * m)
val fib = fibFrom(0, 1)

def computeReprs(min: Int, max: Int) = (for
n <- min to max
f1 <- fib.takeWhile(f => f * f <= n)
f2 <- fib.dropWhile(_ < f1).takeWhile(f => f * f <= n - f1 * f1)
f3 <- fib.dropWhile(_ < f2).takeWhile(f => f * f <= n - f1 * f1 - f2 * f2)
f4 <- fib
.dropWhile(_ < f3)
.takeWhile(f => f * f <= n - f1 * f1 - f2 * f2 - f3 * f3)
if n == f1 * f1 + f2 * f2 + f3 * f3 + f4 * f4
yield (n +: Seq(f1, f2, f3, f4).map(fib.indexOf(_)))).distinct

val reprs = computeReprs(0, max)

def printForMathSE() =
def formatRepr(r: Seq[Int]): String =
if r(0) == 0 then "0 &= F_0^2"
else
s"$${r(0)} &= " + r.tail .filter(_ != 0) .map(i => "F_{" + s"$$i" + "}^2")
.mkString("+")

var counter = 0
val endMarkerSeq = Seq("\\\\\n", "&  ")
def endMarker = { counter += 1; endMarkerSeq(counter % 2) }

extension (reprs: IndexedSeq[String])
def myMkString(endMarker: => String, acc: Seq[String] = Seq()): String =
reprs match
case IndexedSeq()     => acc.mkString
case IndexedSeq(repr) => (acc :+ repr).mkString
case IndexedSeq(repr, _*) =>
reprs.tail.myMkString(endMarker, acc :+ repr :+ endMarker)

println("\\begin{align}")
println(reprs.takeWhile(_(0) <= 50).map(formatRepr).myMkString(endMarker))
println("\\end{align}")

val partition = (0 to max).partition(k => reprs.exists(r => r(0) == k))
println(s"integers with repr:$${partition(0).mkString(", ")}") println(s"integers without repr:$${partition(1).mkString(", ")}")
end printForMathSE

printForMathSE()
• Those would both probably be good additions to OEIS Commented Jul 19, 2023 at 20:03
• Thanks for the suggestion. I will try to optimise the code to compute at least a few more thousand and then see if the OEIS wants it @Burnsba Commented Jul 20, 2023 at 3:42
• @Calvin You can take a look at my answer where the first 12 553 integers are linked. Commented Jul 20, 2023 at 17:26
• @infinitezero Well that's certainly more than mine :) I will add your code to the OEIS proposal? Commented Jul 20, 2023 at 23:30
• @Calvin please feel free to do so. Commented Jul 21, 2023 at 6:16

I've written the bruteforce approach in Mathematica and get results up to $$10^9$$ in a matter of seconds on my machine. I get $$12 553$$ distinct integers, in the range from $$0$$ to $$1254718084=4 F_{22}^2$$. I did however exclude $$F_0 = 0$$ from it, because it seemed pointless.

Here's a log plot, where the $$x$$-axis shows the $$n$$'th integer and the $$y$$-axis its value.

fibonacci = Table[Fibonacci[n]^2, {n, 1, 22}];
reverseFib[n_] :=
SubsuperscriptBox["F", Position[fibonacci, n][[1, 1]] - 1, 2] //
DisplayForm
subsets =
Tuples[fibonacci, 1]~Join~Tuples[fibonacci, 2]~Join~
Tuples[fibonacci, 3]~Join~Tuples[fibonacci, 4];
DeleteDuplicates[
SortBy[{Total[#], Total[reverseFib /@ #]} & /@ subsets,
First]] // TableForm

Since the list is way too exhaustive, I uploaded it to pastebin