My Math Forum Probabilistic methods and equations over $m$-dimensional space.

 December 8th, 2015, 04:37 PM #1 Newbie   Joined: Dec 2015 From: israel Posts: 2 Thanks: 0 Probabilistic methods and equations over $m$-dimensional space. Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand that $n$ is dependent on $p$; you can't demand anything from $m$ except that it's big enough so our space can actually contain $n$ different points): show that there exists a set of linear equations (that look like "$u\bullet v=x$") such that the number of points that don't solve any equation is in the interval $(\frac{1}{2} \pm \delta)n$. there should be $O(p \log n)$ equations. I came across this question why studying probabilistic methods and algorithms, specifically in a chapter on the second moment method. [Please excuse the the bad translation, the questions isn't originally in English. Last edited by ShadiEndrawis; December 8th, 2015 at 04:59 PM.
December 11th, 2015, 08:56 AM   #2
Newbie

Joined: Sep 2013

Posts: 29
Thanks: 0

Quote:
 Originally Posted by ShadiEndrawis Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand that $n$ is dependent on $p$; you can't demand anything from $m$ except that it's big enough so our space can actually contain $n$ different points): show that there exists a set of linear equations (that look like "$u\bullet v=x$") such that the number of points that don't solve any equation is in the interval $(\frac{1}{2} \pm \delta)n$. there should be $O(p \log n)$ equations. I came across this question why studying probabilistic methods and algorithms, specifically in a chapter on the second moment method. [Please excuse the the bad translation, the questions isn't originally in English.
I followed this thread (and your other one) but it seems that none have an answer for. May I ask what text it's from? (Perhaps something not available in English).

I am currently studying combinatorics from Jukna and am familiar (but not great at) probabilistic methods. Sorry to say I do not have an answer for you but I'm curious to learn more about the problem.

-Dave K

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ShadiEndrawis Advanced Statistics 0 December 8th, 2015 04:35 PM Kukkurloom Geometry 7 January 14th, 2015 12:51 PM edunwaigwe@yahoo.com Economics 1 December 26th, 2012 04:57 AM OriaG Calculus 2 September 4th, 2012 12:23 PM elim Abstract Algebra 4 April 29th, 2010 10:52 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top