Sublinear Homomorphism Property Testing Counter Example

Question

This is a homework question, so I'm not looking for answers, just general guidance.

I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of homomorphisms from $\left(\mathbb{Z}_{n}, +\right)$ to $\left(\mathbb{Z}_{n}, +\right)$ (where + is the modulo addition) in particular.

Since $$f:\mathbb{Z}_{n}\to\mathbb{Z}_{n}\ is\ a\ homomorphism\iff\forall x\in\mathbb{Z}_{n}:\ f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$$ (I've managed to prove that), it is suggested to property test $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$.

To counter that suggestion it is said that for a sufficiently large $n$, $$f:\begin{array}{lll} \mathbb{Z}_{n} & \to & \mathbb{Z}_{n}\\ x & \mapsto & x\ \left(mod\ \left\lceil \sqrt{n}\right\rceil \right) \end{array}$$ maintains $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$ for $1-\frac{1}{\sqrt{n}}$ fraction of the $x\in\mathbb{Z}_{n}$ (managed to prove that), but that $f$ is $1-\frac{1}{\sqrt{n}}$-far from any homomorphism (where $\epsilon$-far means that in order to get a homomorphism out of $f$ we have to change at least $\epsilon n$ outputs of $f$).

We're asked to show a counter example of a function that passes the test for $1-o\left(1\right)$ fraction of the inputs, but is $\frac{1}{100}$-far from homomorphisms, which is a bit easier.

So I wanted to show $f$ as my example. I managed to prove what I wrote so far, but I'm still trying to prove $f$ is $1-\frac{1}{\sqrt{n}}$-far.

What I've tried:

Assume by contradiction that $\delta\left(f\right)<n-\sqrt{n}$ (where $\delta\left(f\right)$ is the distance from homomorphisms), that is there exists $h$, an homomorphism, with less than $n-\sqrt{n}$ different (compared to $f$) outputs.

I've divided into 2 cases.

First case is $h\left(1\right)=f\left(1\right)$ which means $h\left(1\right)=1$. It is easy to get a contradiction this way, since then there exists $x>\sqrt{n}$ such that $h\left(x\right)=f\left(x\right)$ (otherwise, contradiction to $\delta\left(f\right)<n-\sqrt{n}$). Since $h$ is a homomorphism, we get $$h\left(x\right)=\underset{i=1}{\overset{x}{\sum}}h\left(1\right)=\underset{i=1}{\overset{x}{\sum}}1=x\neq f\left(x\right)$$

Now the other case where $h\left(1\right)\neq f\left(1\right)$ is where I'm stuck. It's hard for me to get intuition since apparently this is only true for large $n$'s, which makes it hard to look at basic examples. I'm not even sure dividing to these cases is the best approach, and would love some help. Thanks!

Edit:

As requested, a link to the survey by Ronitt Rubinfeld. Only managed to find it in ps format.

Answer 1

Thanks to the help in the comments I was able to unfixate and find an answer to the question. I prove $\delta\left(f\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$.

Let $h:\mathbb{Z}_{n}\to\mathbb{Z}_{n}$ be an homomorphism.

• If $h\left(1\right)=f\left(1\right)$ then $h\left(1\right)=1$ and h is the identity function, since $h\left(0\right)=0$ and $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ due to homomorphisms definition and properties. We get $\delta\left(f,h\right)=1-\frac{1}{\sqrt{n}}\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$ (since they disagree on $n-\sqrt{n}$ values).

• Otherwise, $h\left(1\right)\neq f\left(1\right)$, that is $h\left(1\right)\neq1$. Assume by contradiction that exists $x\in\mathbb{Z}_{n}$ such that $h\left(x+1\right)=h\left(x\right)+1$, but due to homomorphisms definition we get $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ which is a contradiction to $h\left(1\right)\neq1$. Since our function $f$ maintains that $$h\left(x+1\right)=h\left(x\right)+1$$ for $x\in\mathbb{Z}_{n}\backslash\left\{ q\sqrt{n}|0\leq q\leq\sqrt{n}-1\right\}$ , which means $n-\sqrt{n}$ “bad” pairs of $x$ and $x+1$. This means that in order to get any homomorphism, including $h$, we have to change at least one value for each pair, which means at least $\frac{\sqrt{n}-1}{2}$ values changed for each interval $\left[q\sqrt{n},\left(q+1\right)\sqrt{n}\right)\cap\mathbb{Z}_{n}$ (where $0\leq q\leq\sqrt{n}-1$), otherwise due to to the pigeonhole principle we have two consecutive values that are unchanged which is again a contradiction since then $h\left(x+1\right)=h\left(x\right)+1$. So in total we have at least $$\sqrt{n}\frac{\sqrt{n}-1}{2}=\frac{n-\sqrt{n}}{2}$$ values changed, which means $$\delta\left(f,h\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$$