My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
ShadiEndrawis is offline  
 
December 11th, 2015, 08:56 AM   #2
Newbie
 
Joined: Sep 2013

Posts: 29
Thanks: 0

Quote:
Originally Posted by ShadiEndrawis View Post
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
dkotschessa is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

Tags
$m$dimensional, equations, methods, probabilistic, space



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
question about probabilistic methods and isolation lemma. ShadiEndrawis Advanced Statistics 0 December 8th, 2015 04:35 PM
Two intersecting planes in three-dimensional space Kukkurloom Geometry 7 January 14th, 2015 12:51 PM
Equation of a cylinder in 3 dimensional space. edunwaigwe@yahoo.com Economics 1 December 26th, 2012 04:57 AM
Vectors in three dimensional space OriaG Calculus 2 September 4th, 2012 12:23 PM
A infinite dimensional linear space elim Abstract Algebra 4 April 29th, 2010 10:52 AM





Copyright © 2019 My Math Forum. All rights reserved.