Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

An argument for "Brocard's problem has finite solution"

  1. Apr 14, 2015 #1
    Brocard's problem is a problem in mathematics that asks to find integer values of n for which
    $$x^{2}-1=n!$$
    http://en.wikipedia.org/wiki/Brocard's_problem.
    According to Brocard's problem
    ##x^{2}-1=n!=5!*(5+1)(5+2)...(5+s)##
    here,##(5+1)(5+2)...(5+s)=\mathcal{O}(5^{r}),5!=k##. So,
    ##x^{2}-1=k *\mathcal{O}(5^{r})##
    Here,##\mathcal{O}## is Big O notation. For every rational number x , there is a rational r( since k is a constant, if x is increased, r has to be increased to balace the equation). It is a "one-to-one"
    relation, so there exists a "well-defined" function f(x), so ##r=f(x)##
    ##x^{2}-1=k *\mathcal{O}(5^{f(x)})##

    **Claim:** Above equation can not have infinite solution, becuase change rate of ##\mathcal{O}(5^{f(x)})## is much bigger than ##x^{2}-1## ,

    $$\frac{d}{dx}x^{2} <<\frac{d}{dx} \mathcal{O}(5^{f(x)})$$
    if ##f(x) = {2 \over \log 5}\log x## then, ##5^{f(x)} = \mathrm e^{f(x) \log 5} = \mathrm e^{2 \log x} = x^2## but, ##{2 \over \log 5}\log x## is only once integer (when, x=5), if Brocard's problem has infinte solution then f(x) must have infinite integer values. So, ##f(x) \neq {2 \over \log 5}\log x##.


    So, after certain value of x, the equation will not hold.



    **Why the above argument is not correct? what are the flwas?**
    ** you can use other integer value instead of 5.
     
    Last edited by a moderator: Apr 14, 2015
  2. jcsd
  3. Apr 14, 2015 #2

    Mark44

    Staff: Mentor

    This part of what you wrote --
    -- is not true.
    ##\frac 2 {log 5} log x## is an integer for ##x = 5, 5^2, 5^3, ..., 5^n, ...##, for any positive integer power of 5.
     
  4. Apr 14, 2015 #3
    if $$f(x) = {2 \over \log 5}\log x$$ then, $$5^{f(x)} = \mathrm e^{f(x) \log 5} = \mathrm e^{2 \log x} = x^2$$ so, x has to be $$5^m$$ and the equation becomes,$$5^{2m}-1=k *\mathcal{O}(5^{r})=n!\Rightarrow n!+1=5^{2m} $$, implies n!+1 is divisible by 5, which is impossible.

    Are you ok with the rest of the part?
     
    Last edited: Apr 14, 2015
  5. Apr 14, 2015 #4

    Mark44

    Staff: Mentor

    No, as I don't follow some of what you're doing.
    How did you get r? Shouldn't the line where r appears be ##(5 + 1)(5 + 2) ...(5 +s)## be equal to ##\mathcal{O}(5^s)##? There are s terms in the product on the left side.

    Also, the big O notation is used to show the limiting behavior of some function, such as in ##x^2 - 3x + 2 = \mathcal{O}(x^2)##. This doesn't say that ##x^2 - 3x + 2 = x^2##, only that ##\lim_{x \to \infty} x^2 - 3x + 2 = Mx^2## for some constant M (which in this case would be 1).
     
  6. Apr 15, 2015 #5
    s could be r, it covers all cases, you can consider s=r.

    $$ x^{2}-3x+2 \neq x^{2} $$ but the growth of $$ x^{2}-3x+2 $$ depend on $$x^{2}$$, eventually $$\mathcal{O}(5^{f(x)})$$ has bigger growth than $$x^{2}$$ so, it is not possible to hold the equation after certain x.

    Would you elaborate your objection please ?
     
  7. Apr 15, 2015 #6

    Mark44

    Staff: Mentor

    My objections have been pretty clear (I believe). If you want people to follow your proof, you need to remove all of the things that are either wrong or confusing. So far, these have been:
    1. Your assertion in post #1 that ##\frac 2 {log(5)} log(x)## has only one solution. (After I showed you this was not true, you revised your work.)
    2. Your statement that 5!(5 + 1)(5 + 2)...(5 + s) = ##\mathcal{O}(5^r)##. If I understand your thinking, the right side should have been ##\mathcal{O}(5^s)##. To come along later and say that you could consider r = s doesn't do much to help one understand what you're doing without some explanation of how s and r relate to each other.
    3. (Not mentioned before) 5!(5 + 1)(5 + 2)...(5 + s) = (5 + s)! Since factorials grow faster than exponential functions, I don't see how you can say (5 + s)! = ##\mathcal{O}(5^s)##. For example, 12! = 479,001,600 while 512 = 244,140,625. For larger numbers n, n! is even larger than 5n.
     
  8. Apr 15, 2015 #7
    point 1: it is sorted now, I believe.

    In your last point, you misinterpreted,
    True, but I am using big Oh notation, that means $$\mathcal{O}(5^{r})$$ has other terms, those term(all together) will make n!, I am using $$\mathcal{O}(5^{r})$$ because , the growth of the expression $$(5+1)(5+2)...(5+s)$$ depends on $$\mathcal{O}(5^{r})$$.

    point 2: s is due to your point 3 , if I wrote r, you would come up with point 3 (as you have now), to make the visualization, s is introduced. For the time being please , consider s=r.
     
  9. Apr 15, 2015 #8

    Mark44

    Staff: Mentor

    I think you misunderstand what "big-oh" notation means. See http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition. If there are other terms besides ##5^r## they have to be of lower significance than ##5^r##.

    If s = r, then my point 3 stands; namely that 5!(5 + 1)(5 + 2) ... (5 + s) = (s - 5)!, which grows much faster than ##5^r = 5^s##.

    If s and r and different, then you need to explain how they relate to each other, if at all.
     
  10. Apr 16, 2015 #9
    ##(x+1)(x+2)=g(x)## produces a polynimial ##(x+1)(x+2)=x^{2}+3x+2=g(x)## is ## \mathcal{O}(x^{2}) ## here 3x+2 is not written in ## \mathcal{O}(x^{2}) ##.
    Similarly,##(5+1)(5+2)...(5+s)=h(s)## will produce a polynomial and ##h(s)## is ## \mathcal{O}(5^{s}) ##
    Like, the example of g(x), remaining term of h(s) is not included in ## \mathcal{O}(5^{s}) ##.
    Big oh notation is frequently used in complexity theory, if an algorithm has time complexity of ##x^{2}+3x## , then the complexity can be writtrn as ## \mathcal{O}(x^{2}) ## since growth of other terms are less than ## \mathcal{O}(x^{2}) ## or it can be said that the growth of fuction depends less on those term.


    ##5!(5 + 1)(5 + 2) ... (5 + s)## may grow much faster than ##5^s## but not ## \mathcal{O}(5^{s}) ##, you cant ignore remainig term which are "have to be of lower significance than ##5^s## ".
    you dont know what ##s## is. Of course there exists ##M## such that ## \mathcal{O}(5^{M})>n! ##.

    Sill worong??

    [ If ## \frac{d}{dx}q(x) <\frac{d}{dx}\mathcal{O}(5^s)## then
    ## \frac{d}{dx}q(x) <\frac{d}{dx} \mathcal{O}(5^s)< \frac{d}{dx}5!(5 + 1)(5 + 2) ... (5 + s) ## since
    ##\mathcal{O}(5^s)< 5!(5 + 1)(5 + 2) ... (5 + s) ##
    Where ##s=f(x)##, so ##5!(5 + 1)(5 + 2)..(5+s)## is also a fuction of x.]
     
    Last edited: Apr 16, 2015
  11. Apr 16, 2015 #10

    Mark44

    Staff: Mentor

    Yes, of course.
    You haven't told me anything here that I didn't already know.

    I say that you can ignore them. Can you tell me what these "lower significance terms" are?
    Yes. You have told me that I can take s = r. Are these equal or aren't they?

    This is gibberish. how can you take the derivative, with respect to x, of something that is not a function of x?
     
  12. Apr 16, 2015 #11
    If you multiply ##(5+1)(5+2)...(5+s)##, there will be terms, among them, ## 5^{s} ## has the bigger growth than other terms("lower significance terms"). If ## 5^{s} ## has growth bigger than right hand side of the original equation, then ##(5+1)(5+2)...(5+s)## has bigger growth than the rifgt hand side since, ##5^{s}<5!(5+1)(5+2)...(5+s)##.
    I am writing ##\mathcal{O}(5^{s})## for writing convenience , I am not ignoring remaining term.


    yes they are , s/r is a function of x (but I dont have an explicit formula using x variable).
    That was an example to show that
    ##\mathcal{O}(5^{M})<n!## is not true always.
    if you agree on s=r , then s is a function of x, as earlier r was difined to be a function of x.
     
    Last edited: Apr 16, 2015
  13. Apr 16, 2015 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It is still unclear what that means, but I don't think it is true. There is a term s! which exceeds 5s for s>11.

    The whole argument is unclear to me. For every n!, there is an x such that x2 > n!+1, and there are x such that x2 < n!+1. How do you rule out the case in between?
    The thread got very messy with all the unconventional notation, r/s confusion and so on. Using notation in a way no one else understands might be convenient for you, but not for others. Could you make a new post that is easier to read please?
     
  14. Apr 16, 2015 #13
    these x , n dont need to be considered since they can not be brocards problems solution.

    s is a function of x, s! will have bigger growth than right hand side, what I proposed still holds.
    Sorry for that, I will consider , but I fear , the mess will continue . Reader should clear there confusion from the start, serially, not haphazardly, if you ask about line, which is after some line I would assume, you understood/agreed previous line. But, then if you ask about previous line , it is really hard to explain.
     
  15. Apr 17, 2015 #14

    Mark44

    Staff: Mentor

    Thread closed. As mfb asked, please start a new thread that is easier to read.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: An argument for "Brocard's problem has finite solution"
  1. Geometric arguments (Replies: 5)

  2. Geometric Argument (Replies: 5)

  3. Complex arguments (Replies: 2)

Loading...