<p>We improve bounds on the degree and sparsity of Boolean functions representing the Legendre symbol as well as on the <i>N</i>th linear complexity of the Legendre sequence. We also prove similar results for both the Liouville function for integers and its analog for polynomials over <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_783_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathbb {F}_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>, or more general for any (binary) arithmetic function which satisfies <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_783_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">\(f(2n)=-f(n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>-</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12095_2025_783_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="85" /> </InlineMediaObject> <EquationSource Format="TEX">\(n=1,2,\ldots \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> </mrow> </math></EquationSource> </InlineEquation></p>