8
$\begingroup$

I'm having problem trying to determine if all square numbers (1, 4, 9, 16, ...) written in binary form (1, 100, 1001, ...) is a regular language.

After some attempts to find a common pattern of those numbers, I found out that for any square number $n^2$, $n^2 mod 4$ either equals to 0 or 1, and so I am able to draw a DFA graph with 4 states to recognize this language. But apparently, the DFA I drew actually recognizes a superset of the square number language in question. I'm stuck here.

Anyone could give me some clues on this problem? If it's not a regular language, how should I prove it?

I am also very interested to know how I should approach to this kind of question the best way in the future. I know that in many cases, if we have the intuition that the automata has to keep a track of what is has seen already (like $a^i b^i$), then there's an undetermined states needed for the automata to compute, thus it's not finite or regular. We can then use Pumping lemma to prove it's not regular. However, I can't tell if this language is regular yet, so I don't really have an idea what to do next.

Thanks!

$\endgroup$
  • $\begingroup$ It's certainly not enough to check whether your input is congruent to $0$ or $1$ mod $4$, since, e.g., $5\equiv 1\mod 4$ but $5$ isn't a square. My guess is that the language isn't regular, since it feels like you need to remember the whole input to know if it's a square or not (this is just an intuition and nothing like a proof). $\endgroup$ – David Richerby Nov 17 '17 at 16:13
  • 1
    $\begingroup$ The "general approaches" part of your question is covered by our reference questions. $\endgroup$ – David Richerby Nov 17 '17 at 16:15
  • $\begingroup$ @DavidRicherby Those are very general. I don't think we had the generalization of this particular question to sets defined by arithmetic before. $\endgroup$ – Gilles Nov 17 '17 at 22:13
9
$\begingroup$

Here is a high-tech solution. Denote your language by $L$. Szalay showed that $$ L \cap 10^*10^*1 = \{ 10^n10^{n+2}1 : n \geq 0 \} \cup \{110001, 1000010001\}. $$ From here it's pretty easy to show that $L$ is not regular, by reduction to $\{a^nb^n : n \geq 0\}$.

$\endgroup$
  • $\begingroup$ "reduction from"? $\endgroup$ – Omar Dec 3 '17 at 7:58
  • $\begingroup$ It's an informal term - by reduction to the known irregularity of $a^nb^n$. $\endgroup$ – Yuval Filmus Dec 3 '17 at 12:24
2
$\begingroup$

Well, this is the third time I rewrite this answer. User Yuval Filmus pointed two very very silly mistakes I made in the previous two versions.

Well I finally found a simple solution to the problem. I think it works.

First we have that words of this type:

$1(00)^p1(00)^p001$

Are square numbers.

Proof:

I´ve looked information about square numbers and then I found about "centered octagonal numbers" which are numbers that are formed by layers of multiples of eight, but not the first layer. The first layer is one, the second eight, the third sixteen and so on.

So each layer has an "eight" more than the previous one. The number of eights in a centered octagonal number can be calculated by using gauss formula:

$\frac{n^2 + n}{2}$

We then multiply by eight and add one, this is because the first layer is only a dot.

$\frac{8(n^2 + n)}{2}+1$

Simplyfying:

$4(n^2 + n) + 1$

That formula gets us the odd square numbers for every n.

I´m going to calculate the formula for the number four and all powers of four.

First we square the number, this simply doubles the zeroes of the number. Then we add the number to the product. This puts a "one" at position $\lceil|n|/2\rceil$ starting from the right. $|n|$ is the length of the binary word.

Right now we have words of this form:

$1(00)^p1(00)^p0$

We multiply by four, this simply adds two zeroes at the end of the number. Finally we sum one. We are done.

Pumping

I set $i=0$.

First the easy case

If we let $x$ empty, then we take the number one and one or more zeroes. This gives us words with hamming weight two (the number of ones is two). There is only an uneven number with hamming weight two, the number nine (the only odd square number of the form 2n + 1 is 9, I saw this in wikipedia: see here). As all numbers we are pumping are bigger than nine, we proved this case.

Hard case

We let the first "one" in its place and we take out zeroes only. We can take out up to $p-1$ zeroes.

The word will look like this:

$10(00)^m1(00)^n001$.

Where $m$ and $n$ are integers bigger or equal to one and $n > m$

I will first believe that the number obtained is a square, then I will show that´s false:

Since we know that all odd square numbers can we obtained with this formula:

$4(n^2 + n) + 1$

We start decomposing the number, we substract one, this simple sets the last one to zero and then, we divide by four, this removes two zeroes at the end of the binary word.

Then we´ll have words like this:

$10(00)^m1(00)^n0$, $n$ and $m$ are integer numbers bigger or equal to one and $n > m$. These words are a prefix of the complete word.

Since we are believing that this chain is part of a square number, the word had to be formed by doing this formula:

$(n^2 + n)$

$n$ can´t be even

We'll look again at this formula:

$n^2 + n$

Since we are believing that the words we have pumped are square numbers. We call the words we have pumped $m$ and we have that:

$m = n^2 + n$

Also, we have that $m$ can be represented as the sum of two binary numbers, $m_1$ and $m_2$, each of them is a power of two. And we have that $\sqrt{m_1} < m_2$ and $m_1 > m_2$

The first thing that we notice is that $n$ has to be less than $m_2$. This is because $m_2$ is bigger than the square root of $m_1$, if $n$ was equal to $m_2$, then $n^2$ will be bigger than $m$.

Now, when we square an even binary number, we have that the number squared has "more zeroes" to the right of the first "one" than the original number had. So "the rightmost one" inside $n^2$ is at the left of the "rightmost one" inside $n$. If we add $n$ to $n^2$ , we have that the "rightmost one" inside $n^2 + n$ is the "rightmost one" in $n$. Since $n$ is smaller than $m_2$. We have that the "rightmost one" inside $n^2 + n$ is to the right of the "rightmost one" in $m$. Therefore $m \neq n^2 +n$ . But since we said that $n^2 + n = m$ we have reached a contradiction and therefore $n$ can´t be even.

$n$ can´t be uneven

Again, we have that $m$ is a number made by adding $n$ to $n^2$, so $m = n^2 + n$

Then we notice that $(n + 1)^2 - (n + 1) = n^2 + n$; This is because:

$(n + 1)^2 - (n + 1) = n^2 + 2n + 1 -n -1$;

And then:

$(n + 1)^2 - (n + 1) = n^2 + n$.

Another way to see this, is to imagine $n^2$ as a square with sides of length $n$. This square is formed by smaller squares of size one. Then, when we add $n$ squares of size one to the previous square, the previous square is now a rectangle whose sides are $n$ and $n+1$. Now, we can imagine $(n + 1)^2$ as another square with sides of of length $n + 1$. This square is also formed by smaller squares of size one. If we remove $n + 1$ squares to it, we have a rectangle of sides $n$ and $n+1$.

We have that $n + 1$ is an even number and the proof follows the same as before for all odd numbers $n$ less than $m_2 - 1$

Again, when we square an even binary number, we have that the number has "more zeroes" to the right of the first "one" than the original number had. So "the rightmost one" inside $(n + 1)^2$ is at the left of the "rightmost one" inside $n + 1$. If we substract $n + 1$ to $(n + 1)^2$, we have that the "rightmost one" inside $n^2 + n$ is the "rightmost one" in $n + 1$. Since $n + 1$ is smaller than $m_2$. We have that the "rightmost one" inside $n^2 + n$ is to the right of the "rightmost one" in $m$.

If $n = m_2 - 1$.

Again, we have that $n^2 + n = (n + 1)^2 - (n + 1)$. Since $m_2^2$ ($m_2$ squared) is a number that is a power of two, it has only a single leading "one" and then zeroes. When we substract $m_2$ to $m_2^2$, we are turning all zeroes to the left of the leftmost digit of $m_2$ inside $m_2^2$ into "ones" and the resulting number is not like the words we are pumping, there should be at least a "zero of separation" between the ones.

Therefore $m \neq n^2 +n$ . But since we said that $n^2 + n = m$ we have reached a contradiction and therefore $n$ can´t be uneven.

As $n$ can´t be even or uneven, we have that $n$ doesn´t exist as an integer. Therefore the words we pumped are not the product of the formula for odd square numbers. Since all the words we are pumping are odd, they can´t be square numbers.

$\endgroup$
  • 1
    $\begingroup$ You cannot apply the pumping lemma to $1(00)^p$ in order to show that your language isn't regular, since $1(00)^p$ can be pumped. Same applies to $(00)^p1$ in the reverse language. $\endgroup$ – Yuval Filmus Nov 22 '17 at 16:55
  • $\begingroup$ You cannot choose $y$ in the pumping lemma. The pumping lemma only states that some $y$ works. In order to show that the language isn't regular, you have to show that no $y$ works. $\endgroup$ – Yuval Filmus Nov 22 '17 at 16:58
  • $\begingroup$ @yuvalFilmus You are right $\endgroup$ – rotia Nov 22 '17 at 17:00
  • 2
    $\begingroup$ You state that an even number remains even upon division by 2, but that's not always the case. $\endgroup$ – Yuval Filmus Nov 30 '17 at 23:40
  • 2
    $\begingroup$ I notice that you've made about 15 edits in the past 2 days. It's great that you want to improve your answer, and I'd love to see you keep doing that. However, it might be a little unfair to other questions to keep bumping this one to the top of the front page each time you edit here. Do you think you might be able to batch your edits (maybe writing them offline, say with stackedit.com) so you make only a few edits per day? I don't want to discourage you from editing your answer to improve it, but I'm wondering if there might be some happy medium possible. Thanks for listening! $\endgroup$ – D.W. Dec 5 '17 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.