mersenneforum.org Problem of the Month
 Register FAQ Search Today's Posts Mark Forums Read

2011-11-16, 23:44   #67
ccorn

Apr 2010

22·3·13 Posts

Quote:
 Originally Posted by literka You were right, there is an error in the text. I should be : Let C(n,k) denote binomial coefficient C(n,k)=n!/[k! * (n-k)!]. Operator "<=" means "less or equal". Let a1>=a2>=...>=a2n>=0 Let { bi } (1<=i<=2n) be a Bernoulli sequence of independent random variables i.e. they are independent and P(bi = 1) = P(bi = -1) = 0.5 Let a random variable x be defined as x=abs(b1*a1+b2*a2+...+b2n*a2n) where abs(y) means absolute value of y. Then P(x<=a1)>=C(2n,n)/(2^2n)
So this is essentially the original problem you posted in this thread, but with the maximum norm instead of the euclidian norm for (a1,...a2[I]n[/I]) and with a weaker probability estimate, bounded below by asymptotically $\frac{1}{\sqrt{\pi n}}$ (using Stirling's asymptotic formula). If I have misunderstood that, please correct me.

Last fiddled with by ccorn on 2011-11-16 at 23:47

2011-11-17, 00:03   #68
literka

Mar 2010

26×3 Posts

Quote:
 Originally Posted by ccorn So this is essentially the original problem you posted in this thread, but with the maximum norm instead of the euclidian norm for (a1,...a2[I]n[/I]) and with a weaker probability estimate, bounded below by asymptotically $\frac{1}{\sqrt{\pi n}}$ (using Stirling's asymptotic formula). If I have misunderstood that, please correct me.
I formulated and proved this to have a tool for a main problem. After some time I stopped trying to find a main proof, since it was taking me to much time.
Your geometrical interpretation of a problem was known before. In fact, I saw this problem quoted this geometrical way.

2011-11-29, 01:27   #69
ccorn

Apr 2010

22·3·13 Posts
Asymptotic plausibility of Literka's first problem

Quote:
 Originally Posted by ccorn Geometrically, this means that at least half of all the vertices of an n-dimensional hypercube (all coordinates +/-1) are not farther than unit distance from an arbitrary (n-1)-dimensional hyperplane containing the origin. The hyperplane's normal vector is (a1,...,an).
The hypercube's (n-1)-dimensional bounding sphere S[I]n[/I]-1 has radius $\sqrt{n}$. Let A[I]n[/I]-1 be the subset of points of S[I]n[/I]-1 that have distance at most 1 from the central hyperplane with normal vector (a1,...,an). (For n=3, imagine the surface of a striped billiard ball.) The claim of Literka's first problem is that at least half of the hypercube's vertices are in the stripe A[I]n[/I]-1.

The hypercube has lots of symmetries. In particular, its vertices are spaced evenly across S[I]n[/I]-1.* Therefore, the ratio fn of the measures of A[I]n[/I]-1 and S[I]n[/I]-1 provides sort of an expected value for the fraction of all hypercube vertices that belong to A[I]n[/I]-1. If fn were to drop below 1/2 for some n, this would suggest that there are counterexamples.

As it turns out (left as an exercise for the readers), $f_n = \mathrm{I}(\frac{1}{n};\frac{1}{2},\frac{n-1}{2})$ where I(z;a,b) denotes the Regularized (incomplete) Beta function. One finds that $\lim_{n\to\infty} f_n = \mathrm{erf}(\frac{1}{\sqrt{2}})\approx 0.68$, the within-1-standard-deviation probability of a normal distribution. This does not prove Literka's first problem, but at least it does not indicate a contradiction.

*: "Spaced evenly" meaning that the Voronoi regions (on S[I]n[/I]-1) of the vertices are all congruent.

Last fiddled with by ccorn on 2011-11-29 at 02:01

 2012-03-21, 13:45 #70 literka     Mar 2010 26·3 Posts A problem just for fun. Let f be a concave function (example of concave function is f(x)= log x ) defined on the interval [0,1]. Let |f|1 be the first norm of f. Let |f|2 be the second norm of f. First norm means integral of absolute value of f over [0,1]. Second norm means square root of the integral of f2 over [0,1]. With the above assumptions show that sqrt(2)*|f|1 >= |f|2 Have a fun. Hint: solution is very simple. Last fiddled with by literka on 2012-03-21 at 13:56
 2012-03-21, 17:16 #71 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-03-21, 17:31   #72
literka

Mar 2010

26×3 Posts

Quote:
 Originally Posted by Dubslow You mean f'' < 0 for concave?
Yes, but only in the case function has a second derivative. (My theorem concerns broader class of functions.) I used a definition as it is in http://en.wikipedia.org/wiki/Concave_function.
Sorry, I forgot to add an assumption f>=0, of course.
I figured out this problem long time ago, when I was a student. That is why I can hardly remember it. Of course without the assumption f>=0 theorem is not true.

Last fiddled with by literka on 2012-03-21 at 17:36

 2012-03-23, 18:42 #73 literka     Mar 2010 26·3 Posts I realized that there is probably an open problem associated with the above theorem. So I decided to write a webpage with a proof of this theorem and with a problem, which I believe is an open problem. See my page www.literka.addr.com/mathcountry/concave.htm. Last fiddled with by literka on 2012-03-23 at 18:51
2012-03-24, 13:01   #74
sascha77

Jan 2010
germany

2×13 Posts

Quote:
 Originally Posted by chris2be8 You can find a monthly problem at http://domino.research.ibm.com/Comm/...ges/index.html Most take more effort to solve than I have free time though. Chris K

Thanks for the interesting link !
I love such puzzles. (that are easy to understand, but not so easy to solve)

I also have a problem, that has a relation to mersenne numbers.
But maybe the problem is just "a problem of the minute". I do not know, yet.

1.) Let p be a prime number with p>=3 and p is not a Wieferich prime.
(Wieferich prime p is prime number with property: $2^{p-1} \equiv 1 \;\;(\;mod p^2\;)$

2.) Let k be a natural number with k>=2

Is it possible to chose p and k as descibed in (1) and (2), so that
$2*k*p^{2}+1$ is prime and satisfies the congruence:

$2^p \equiv 1 \;\;(\;mod\; 2*k*p^{2}+1\;)$

2012-03-24, 13:56   #75
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by sascha77 Thanks for the interesting link ! I love such puzzles. (that are easy to understand, but not so easy to solve) I also have a problem, that has a relation to mersenne numbers. But maybe the problem is just "a problem of the minute". I do not know, yet. 1.) Let p be a prime number with p>=3 and p is not a Wieferich prime. (Wieferich prime p is prime number with property: $2^{p-1} \equiv 1 \;\;(\;mod p^2\;)$ 2.) Let k be a natural number with k>=2 Is it possible to chose p and k as descibed in (1) and (2), so that $2*k*p^{2}+1$ is prime and satisfies the congruence: $2^p \equiv 1 \;\;(\;mod\; 2*k*p^{2}+1\;)$
Code:
forprime(p=1,1000,for(k=2,100*p,if((2^p)<(2*k*p^2+1),print(p","k);break())))
the least p that seems to have any hope of solution for k>=2 is p=11.

2012-03-24, 14:43   #76
sascha77

Jan 2010
germany

2×13 Posts

Quote:
 Originally Posted by science_man_88 Code: forprime(p=1,1000,for(k=2,100*p,if((2^p)<(2*k*p^2+1),print(p","k);break()))) the least p that seems to have any hope of solution for k>=2 is p=11.

I see. From what I understand $2^p < 2*k*p^2+1$ is your break-condition.
But you can also set a maximum limit for k direct.
Maybe this speeds up the calculation a little bit ?

$2^{p} \equiv 1 \;(mod \;2*k*p^{2}+1)$

<-> $2*k*p^{2}+1 \;divides \;2^{p}-1$

Therefore: $2^{p}-1 \ge 2*k*p^{2}+1$

$2^{p} \ge 2*k*p^{2}+2$

$2^{p-1}-1 \ge k*p^{2}$

$\frac{2^{p-1}-1}{p^{2}} \ge k$

-> so k must be smaller as $\frac{2^{p-1}-1}{p^{2}}$

2012-03-24, 14:48   #77
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by sascha77 I see. From what I understand $2^p < 2*k*p^2+1$ is your break-condition. But you can also set a maximum limit for k direct. Maybe this speeds up the calculation a little bit ? $2^{p} \equiv 1 \;(mod \;2*k*p^{2}+1)$ <-> $2*k*p^{2}+1 \;divides \;2^{p}-1$ Therefore: $2^{p}-1 \ge 2*k*p^{2}+1$ $2^{p} \ge 2*k*p^{2}+2$ $2^{p-1}-1 \ge k*p^{2}$ $\frac{2^{p-1}-1}{p^{2}} \ge k$ -> so k must be smaller as $\frac{2^{p-1}-1}{p^{2}}$
2*m*p+1 | 2^p-1 so really all your asking is can 2*m*p+1 divide 2 Mersennes but with only one p m=k*p is what you can check for.

 Similar Threads Thread Thread Starter Forum Replies Last Post Aillas PrimeNet 48 2012-02-15 19:17 cheesehead Soap Box 0 2009-01-24 07:59 em99010pepe No Prime Left Behind 5 2008-02-24 14:37 ltd Prime Sierpinski Project 22 2006-03-02 17:55 JuanTutors Lounge 6 2005-02-28 22:59

All times are UTC. The time now is 23:09.

Mon Feb 6 23:09:06 UTC 2023 up 172 days, 20:37, 1 user, load averages: 0.88, 1.15, 1.09