In an earlier note (arXiv:2606.11090) I showed that the border determinantal complexity of the power sum x_1^d + ... + x_N^d is ?(Nd). The proof counted the simple solutions of an explicit polynomial system and compared that number with what a small determinant can produce. This left two questions. Does the argument work for other polynomials? And how far can it be pushed?

This article answers both. For the first question, the power sum turns out not to be special. What the argument really counts is the smooth points of the zero set whose tangent hyperplanes pass through some fixed generic points. Every smooth form of degree d in N variables has exactly d(d-1)^(N-2) of these. A determinant of size m has at most about (4em/N)^(N-1). So any polynomial with an affine-linear restriction to a smooth form has border determinantal complexity at least (N-1)(d-1)/(4e), and at least (N-1)(d-1)/(2e) in the symmetric model.

This lets me move from power sums to more natural families. For the homomorphism polynomial of a connected bipartite graph F with q labels, I get ?(q|E(F)|). When F is a path with q^2 edges, the bound is ?(q^3), and this is tight. These polynomials form a VBP-complete family.

For the second question, the answer is that the method does not go much further. I compute the count exactly for generic matrices, and this shows that the constant 4e cannot be improved asymptotically. I then use bounds on the topology of linear sections to show that the comparisons of polar counts in Section 6 cannot prove more than O(dN), even when singular strata are taken into account. For the permanent this means at most O(n^3). For the power sum of degree N it means (1+o(1))N^2/(4e), so the bound from the earlier note is the best this approach can give.

The exposition is due to the human author. The mathematical results were obtained in the process of a discussion of lower bounds on the permanent with Claude Fable 5 and later refined and simplified in conversations with Claude Opus 5.5 and ChatGPT Astra.