Contatore di test di proprietà dell'omomorfismo sublineare

Question

Questa è una domanda per i compiti, quindi non sto cercando risposte, solo una guida generale.

Sto esaminando un sondaggio sullineare algoritmi in cui vengono discussi i test di proprietà dell'omomorfismo (gruppo). Il caso degli omomorfismi da $ left ( mathbb {z} _ {n}, + a destra) $ a $ left ( mathbb {z} _ {n}, + a destra) $ (dove + è l'aggiunta del modulo) in particolare.

Da $$ f: mathbb {z} _ {n} to mathbb {z} _ {n} is a homomorphism iff forall x in mathbb {z} _ {n}: f sinistra (x+1 a destra) equiv_ {n} f sinistra (x a destra)+f sinistra (1 a destra) $$(Sono riuscito a dimostrarlo), è suggerito al test della proprietà $ f sinistra (x+1 a destra) equiv_ {n} f left (x a destra)+f sinistra (1 a destra) $.

Per contrastare questo suggerimento si dice che per un sufficientemente grande $ n $, $$ f: inizio {array} {lll} mathbb {z} _ {n} & to & mathbb {z} _ {n} x & mapsto & x left (mod a sinistra lceil sqrt {n} destro rceil destro) end {array} $$ mantiene $ f sinistra (x+1 a destra) equiv_ {n} f left (x a destra)+f sinistra (1 a destra) $ per $ 1- frac {1} { sqrt {n}} $ frazione di $ x in mathbb {z} _ {n} $ (è riuscito a dimostrarlo), ma quello $ f $ è $ 1- frac {1} { sqrt {n}} $-far da qualsiasi omomorfismo (dove $ epsilon $-Far significa che per ottenere un omomorfismo da $ f $ Dobbiamo cambiare almeno $ epsilon n $ output di $ f $).

Ci viene chiesto di mostrare un contatore di una funzione che supera il test $ 1-O Left (1 a destra) $ frazione degli input, ma è $ frac {1} {100} $-Far dagli omomorfismi, il che è un po 'più facile.

Quindi volevo mostrare $ f $ come mio esempio. Sono riuscito a dimostrare ciò che ho scritto finora, ma sto ancora cercando di dimostrare $ f $ è $ 1- frac {1} { sqrt {n}} $-lontano.

Quello che ho provato:

Assumere per contraddizione $ Delta Left (f a destra) (dove $ Delta Left (f a destra) $ è la distanza dagli omomorfismi), cioè esiste $ H $, un omomorfismo, con meno di $ n- sqrt {n} $ diverso (rispetto a $ f $) output.

Mi sono diviso in 2 casi.

Il primo caso è $ h sinistra (1 a destra) = f sinistra (1 a destra) $ che significa $ h a sinistra (1 a destra) = 1 $. È facile ottenere una contraddizione in questo modo, da allora esiste $ x> sqrt {n} $ tale che $ h left (x a destra) = f sinistra (x a destra) $ (Altrimenti, contraddizione con $ Delta Left (f a destra)). Da $ H $ è un omomorfismo, otteniamo $$ h left (x a destra) = underset {i = 1} { overset {x} { sum}} h left (1 a destra) = underset {i = 1} { overset {x } { sum}} 1 = x neq f left (x a destra) $$

Ora l'altro caso dove $ h left (1 a destra) neq f sinistra (1 a destra) $ è dove sono bloccato. È difficile per me ottenere intuizione poiché apparentemente questo è vero solo per grandi $ n $, il che rende difficile guardare agli esempi di base. Non sono nemmeno sicuro che dividere con questi casi sia l'approccio migliore e mi piacerebbe un po 'di aiuto. Grazie!

Modificare:

Come richiesto, un link al file Sondaggio di Ronitt Rubinfeld. È riuscito solo a trovarlo in formato PS.