Sublinear only tells that it's $$$o(n)$$$, but subpolynomial emphasizes that it's better than any polynomial ($$$n^c$$$).

Yeah this is some jargon in this field: I think usually "near-linear" is understood as $$$n \operatorname{polylog} n$$$ and $$$n^{1+o(1)}$$$ is referred as "almost-linear".

An interesting fact: The crucial step in the solution of E2 is known as the MacWillams identity in coding theory: Let the generating function of the words in a linear code $$$C \subseteq \mathbb F_2^n$$$ be $$$F_C(x, y) = \sum_{w\in C} x^{n-|w|_1} y^{|w|_1}$$$, then

Where $$$C^\perp$$$ is the dual code $$$C^\perp = \{ v : \langle v, w\rangle = 0, \forall w\in C \}$$$.

Sorry for causing such confusion. I rewrote this part now, which is close to what you presumed. There is no need to maintain some data structure, it's just a 2D table lookup. By the argument of the Corollary, you just need to find the matrix stored in $$$(\lfloor aB/X\rfloor, \lfloor bB/X\rfloor)$$$.

Auto comment: topic has been updated by LorentzianExpanders (previous revision, new revision, compare).

The notion in my blog is aligned with some experts in matrix multiplication, where there is only a slight abuse of the notion: trilinear forms are actually the dual of tensor space ($$$V_1 \times V_2\times V_3 \to F$$$ is $$$V_1^* \otimes V_2^* \otimes V_3^*$$$) but not exactly the tensor space itself. And since we usually only need to care about tensor rank, it is still well-defined, since this quantity is basis-independent.

I didn't learn this algorithm, but it looks like it is a matrix-theoretical style algorithm, while my approach is somehow called the "Krylov method" (pick a vector $$$v$$$ and iteratively compute $$$A^i v$$$). I think usually it will be somehow more clean, but has a larger constant compared to clever matrix operations instead. For example, my algorithm seems to have a larger constant than computing the Hessenberg form, when the goal is to just compute the characteristic polynomial. Maybe one reason is that maintaining a basis is not that cache-friendly.

Yes! This can be extended to a rigorous proof. :)

The pentagonal number theorem is a corollary of the Jacobi triple product

by substituting $$$z = x^{1/2}$$$, $$$q = -x^{3/2}$$$. And this identity can be proved through a pure gf derivation, or a combinatorial way.

My second unrated contest...