@FedorPetrov: Yes, good point. Your observation is useful for providing more counterexamples. The idea of the cyclic matrix is more useful to show in some cases, the matrix is always invertible. For example, it is easy to see for $n$ a prime number, the matrix is always invertible. In this case, the group must be generated by a $n$-cycle by considering the order of an element. And the minimal polynomials of $n$-th root of unity are $x-1$ or $\frac{x^n-1}{x-1}$. And it is not a hard exercise to very find they are not a factor for any $f(x)$ constructed as above.

@MarkWildso: Thanks, I see. I will change the answer.

@PeterMueller Thanks for asking. The $L_\infty$ bounds here is $\infty$. Even considering the function g(x)=xf(x), the possible $L_\infty$ bounds after shift down is possible close to 2.5. Hence it is related but does not answer the question..

Thanks for your answer and reference. I want to consider the solution for $n$ big enough. But you example is very interesting.