mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2011-11-16, 23:44   #67
ccorn
 
ccorn's Avatar
 
Apr 2010

5×31 Posts
Default

Quote:
Originally Posted by literka View Post
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
ccorn is offline   Reply With Quote
Old 2011-11-17, 00:03   #68
literka
 
literka's Avatar
 
Mar 2010

19210 Posts
Default

Quote:
Originally Posted by ccorn View Post
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.
literka is offline   Reply With Quote
Old 2011-11-29, 01:27   #69
ccorn
 
ccorn's Avatar
 
Apr 2010

100110112 Posts
Default Asymptotic plausibility of Literka's first problem

Quote:
Originally Posted by ccorn View Post
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
ccorn is offline   Reply With Quote
Old 2012-03-21, 13:45   #70
literka
 
literka's Avatar
 
Mar 2010

26×3 Posts
Default 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
literka is offline   Reply With Quote
Old 2012-03-21, 17:16   #71
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

You mean f'' < 0 for concave?
Dubslow is offline   Reply With Quote
Old 2012-03-21, 17:31   #72
literka
 
literka's Avatar
 
Mar 2010

19210 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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
literka is offline   Reply With Quote
Old 2012-03-23, 18:42   #73
literka
 
literka's Avatar
 
Mar 2010

3008 Posts
Default

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
literka is offline   Reply With Quote
Old 2012-03-24, 13:01   #74
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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\;)

sascha77 is offline   Reply With Quote
Old 2012-03-24, 13:56   #75
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts
Default

Quote:
Originally Posted by sascha77 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-03-24, 14:43   #76
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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}}
sascha77 is offline   Reply With Quote
Old 2012-03-24, 14:48   #77
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts
Default

Quote:
Originally Posted by sascha77 View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Month of Double Check effort Aillas PrimeNet 48 2012-02-15 19:17
Whiner-of-the-Month cheesehead Soap Box 0 2009-01-24 07:59
One month of NPLB em99010pepe No Prime Left Behind 5 2008-02-24 14:37
Best month ever for PSPs prp effort ltd Prime Sierpinski Project 22 2006-03-02 17:55
New Month's Resolution JuanTutors Lounge 6 2005-02-28 22:59

All times are UTC. The time now is 19:43.


Sat Nov 26 19:43:07 UTC 2022 up 100 days, 17:11, 1 user, load averages: 1.18, 1.22, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔