Prime factors are optimal decomposition for Bootle

[uncomputable]

Bootle's protocol divides the lengths of vectors in each step, until the length is one. Any decomposition works, but we want to send as few elements as possible. In other words, we want the minimal sum of factors, which is the prime factors if I am not mistaken.

Does it make sense to change the example 600 = 10 * 10 * 6 (yielding 42 elements) into 600 = 2^3 * 3 * 5^2 (yielding 23 elements)? Would this help underline the message?

[AdamISZ]

Here's my reasoning, let me know where you differ:

Each matrix we have to send 2n-1 diagonals; the 2n-1 formula includes the main diagonal. Now, for the top level matrix, we already have that value: it's the original commitment A, so arguably we should not include that one element. That means it's (2n-1) for each matrix down the list, where n changes with the dimension of the matrix, but we subtract 1 at the end of the calculation to account for the initial commitment, and also, for the final value we just send each scalar we committed to (so that number is added directly, rather than (2n - 1)).

So if that's right, then for 10x10x6 we'd get: 19 + 19 + 6 - 1 = 43.

And if we used each prime factor one by one we'd get 3 x 3 + 5 + 9 + 5 - 1 = 27

Or if you mean taking the equal prime factors together (you clearly didn't): 15 + 5 + 25 - 1 = 44

(I like your comment about minimizing with actual prime factors, that feels intuitively right though I haven't bothered about looking for a proof).

Been a long time since I looked at this so wouldn't be surprised to be wrong, but let me know how you see it.

[uncomputable]

The original commitment A is known so the main diagonal of the first matrix can be excluded, but we also transform the original problem instance into a smaller one. Each step is self-similar, and the Verifier computes A' which becomes A in the next step. So, in each recursive step we can exclude the main diagonal, yielding (2n - 2) transmitted points per step. In the last step, we simply transmit all vector components.

Looking at the prime factorisation of 600, we get 3 * f(2) + f(3) + f(5) + 5 = 23 where f(x) = (2x - 2). The largest factor should be used in the last step. I don't know exactly why but it yields smaller results.

My intuition why prime factors work best is that primes are by definition the smallest factors of any number, so they achieve the "most" multiplicately speaking with the "least" additively speaking.

(Thinking about it, technically we have to multiply the cost of points by 2, since they have an x- and a y-component, while vector components from the last step are scalars, but let's ignore that for now.)