<p>Suppose <span class="math-container">$x \in \{0,\dots,2n\}$</span>. Then we have <span class="math-container">$((2n)^2 - n) + x$</span> is square if and only if <span class="math-container">$x=n$</span>. This is easily seen to imply that the square function is complete for <span class="math-container">$\mathrm{TC}^0$</span> under <span class="math-container">$\mathrm{AC}^0$</span> Turing reductions.</p>

CC BY-SA 4.0
2021-03-01T15:08:29.600Z
Can you provide why the function is TC0 hard?
User2021
CC BY-SA 4.0
2021-03-01T15:12:12.607Z
Ah it captures threshold or rather equality.
User2021
CC BY-SA 4.0
2021-03-01T08:35:24.633Z
2021-03-01T08:35:24.633Z
Kristoffer Arnsfelt Hansen
<p>Consider the symmetric boolean function
<span class="math-container">$$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$</span></p>
<p>It is implementable in <span class="math-container">$TC^0$</span>.</p>
<p>Is there an <span class="math-container">$ACC^0$</span> implementation?</p>
<p>The reason I ask is there seems to be few tricks which can be deployed.</p>
<ol>
<li><p>Square is sum of consecutive odd numbers.</p>
</li>
<li><p>Square is <span class="math-container">$0$</span> or <span class="math-container">$1$</span> mod <span class="math-container">$4$</span> (checkable by <span class="math-container">$\oplus$</span> gates).</p>
</li>
<li><p>Squares are the set of the integers having odd number of divisors.</p>
</li>
</ol>
<p>Few are available in <a href="https://proofwiki.org/wiki/Category:Square_Numbers" rel="nofollow noreferrer">https://proofwiki.org/wiki/Category:Square_Numbers</a>.</p>
<p>But is there a finite number of tricks which capture the function and place it in <span class="math-container">$ACC^0$</span>?</p>

<circuit-complexity><boolean-functions>
$ACC^0$ implementation of a boolean function
User2021
# $ACC^0$ implementation of a boolean function

(Asked by: username_0 on 2021-03-01)

Consider the symmetric boolean function
$$F(x\_1,\dots,x\_n)=1\iff\sum\_{i=1}^nx\_i\mbox{ is a square}.$$

It is implementable in $TC^0$.

Is there an $ACC^0$ implementation?

The reason I ask is there seems to be few tricks which can be deployed.

1. Square is sum of consecutive odd numbers.
2. Square is $0$ or $1$ mod $4$ (checkable by $\oplus$ gates).
3. Squares are the set of the integers having odd number of divisors.

Few are available in <https://proofwiki.org/wiki/Category:Square_Numbers>.

But is there a finite number of tricks which capture the function and place it in $ACC^0$?

**Tags:** circuit-complexity, boolean-functions


---

## 1 answers

### Answer by username_1 on 2021-03-01. Score: 4 | Accepted answer

Suppose $x \in \{0,\dots,2n\}$. Then we have $((2n)^2 - n) + x$ is square if and only if $x=n$. This is easily seen to imply that the square function is complete for $\mathrm{TC}^0$ under $\mathrm{AC}^0$ Turing reductions.

> **Comments:**
> **username_0**: Can you provide why the function is TC0 hard?  
> **username_0**: Ah it captures threshold or rather equality.  

---

