The thing about a signal that is a single sine, is that you can predict them by two coefficients of which one is = -1.
You have a predictor x(N+1) = x(N) * 2 cos q - x(N-1) and with q fit to pi* 2f/F where f is the sine's frequency and F (>2f) is the sampling frequency, then you are all good - provided that the format can offer high enough precision for that 2 cos q.
... and, well: An "optimal" coefficient would be around 1.65313038269 i.e. 6771.22204748 * 2-12, and although a simple -l2 does not catch it, -pl2 finds 6771 * 2-12. Maybe, for all that I know, 27085 * 2-14 or 54170 * 2-15 would do better, maybe not.
@ktf : out of "curiosity", is it possible to force-feed libflac a given predictor vector and test (6771 * 2-12, -1) vs (27085 * 2-14, -1) vs (54170 * 2-15, -1) on this file?
Asking because - semi-educated guesswork, but I might hit it - the explanation might be as follows:
* for -l2, where there would be a perfect predictor if resolution & accuracy were infinite, this is either "a format resolution issue" limited by the right-shift being at most 15 bits, or "an accuracy issue" where intermediate calculations should use an even more precise variable type.
* when order becomes > 2, we have a uniqueness issue on top. There are several "infinite-precision predictors" that would hit the sine exactly, the number of degrees of freedom should be some k = (order minus two) for a pure tone. With finite precision, that means to walk through that grid to find a benevolent roundoff error. Not sure if that is worth to code - likely the alternative with -e, possibly with a few apodization functions too, works as a "try a few arbitrary ones" with the added benefit that if it finds a good one at lower order, it saves the space a coefficient would take.
But "uniqueness issue on top" does not rule out the resolution issue or the accuracy issue.
So if I am right about this, then question is, does it actually hit the best 2nd order predictor the format can offer. If it does not, then one can scratch one's head over whether the double precision change was enough. If it hits the best available 2nd order predictor, then improving over that is a mess ...
... but, can the algorithm detect whether you are close to a singularity? Because then the following is a thinkable option: if that is detected, invoke a more exhaustive search. And that might be an idea even for more general signals.