Optimal selection for good polynomials of degree up to five

An \((r,\ell )\)-good polynomial is a polynomial of degree \(r+1\) that is constant on \(\ell \) subsets of \(\mathbb F_q\), each of size \(r+1\). For any positive integer \(r\le 4\) we provide an \((r,\ell )\)-good polynomial such that \(\ell =C_rq+O(\sqrt{q})\), with \(C_r\) maximal. This directly provides an explicit estimate (up to an error term of \(O(\sqrt{q})\), with explict constant) for the maximal length and dimension of a Tamo–Barg LRC. Moreover, we explain how to construct good polynomials achieving these bounds. Finally, we provide computational examples to show how close our estimates are to the actual values of \(\ell \), and we explain how to obtain the best possible good polynomials in degree 5. Our results complete the study by Chen et al. (Des Codes Cryptogr 89(7):1639–1660, 2021), providing \((r,\ell )\)-good polynomials of degree up to 5, with \(\ell \) maximal (up to an error term of \(\sqrt{q}\)), and our methods are independent.