Tricki
a repository of mathematical know-how

Recent comments

  • Gurmeet 1 year 17 weeks ago Numerical integration and differentiation

    Angela, I think you missed some coefficients, correct expression should be,

    f'''(x)\simeq\frac{f(x+3\delta)-3 f(x+2\delta)+3 f(x+\delta)-f(x)}{\delta^3}

    And I'm sorry but its really difficult to understand the formula you write for n^{th} derivative. I think the expression you wanted to write is the following-

    f^{(n)}(x)\simeq\Big(\sum\limits_{ k=0}^n (-1)^{n-k}{n \choose k}f(x+k\delta)\Big)/\delta^n

  • g__ 1 year 42 weeks ago Just-do-it proofs

    "It's pretty obvious that you can't cover an open disc with finitely many points and lines, but it is not quite trivial, so here's an easy proof: ..."

    A simpler proof: it is impossible to cover even a circle with finitely many lines, since a line can intersect a circle at at most 2 points!

  • lkozma 2 years 6 weeks ago Extra logarithmic factors

    Only if squares are of the same size, no? It would also work for rectangles with same sizes, right?

  • lkozma 2 years 6 weeks ago Extra logarithmic factors

    In the example proof, instead of squares, isn't it meant to be rectangles equal to each other? If squares are allowed to have different sizes, I don't think it is true that each neighbour of a square must overlap with one of its vertices.

    A question: is there some reference for this problem and proof? I realize this problem asks for bounds on m in terms of n, where n=R(m,m) for intersection graph of rectangles. Was this studied for other special graphs?

  • g__ 2 years 16 weeks ago The tensor power trick

    1. (Approximate counting of \mathsf{\# P} problems in {\mathsf{BPP}}^{\mathsf{NP}})

    Let N(\phi) be the number of satisfying assignments of a Boolean formula \phi. Using the leftover hash lemma, there exists a polynomial time probabilistic algorithm taking oracle for SAT that given a formula \phi outputs with high probability a number a such that

    \frac{1}{2} N(\phi) \leq a \leq 2N(\phi)

    i.e. approximates within factor of 2.

    By replacing \phi with "tensor power" = \phi_1 \wedge \dots \wedge \phi_k, the number of assignments rises to N(\phi^k) = N(\phi)^k. Running the algorithm on this formula,

    \frac{1}{2} N(\phi) \leq a \leq 2N(\phi)^k
    \frac{1}{2^{1/k}} N(\phi) \leq a^{1/k} \leq 2^{1/k} N(\phi)

    and putting k=O(\frac{1}{\epsilon}) we get approximation within factor of \epsilon in time polynomial in \frac{1}{\epsilon} and length of \phi. The algorithm is by Stockmeyer.

    2. (Independent set cannot be approximated to a constant factor)

    For any constant \delta \in (0, 1), \delta-approximating maximal independent set in a graph is \mathsf{NP}-hard. (Taking complement, the same argument goes to clique)

    Proof idea:

    The PCP theorem implies that there is a constant \delta' < 1 such that MAX-3SAT cannot be approximated within \delta'. The usual reduction from 3SAT to independent set takes a formula with m clauses and gives a graph with 7m vertices, where each vertex corresponds to one of 7 ways a clause can be satisfied, and edges correspond to conflicts. Therefore the approximation ratio is preserved, and independent set cannot be approximated within some constant factor. Applying "tensor square" G^2 allows to lower the constant arbitrarily.

  • Angela 2 years 43 weeks ago Numerical integration and differentiation

    Use any value δ, which can be made small enough to approximate the derivitive to an arbitrary number of decimal places.
    f'(x)≃(f(x+δ)-f(x))/δ
    f''(x) ((f(x+2δ)-f(x+δ))-(f(x+δ)-f(x)))/δ=f(x+2δ)-2f(x+δ)+f(x)
    f'''(x) (f(x+3δ)-f(x+2δ)+f(x+δ)-f(x))/δ
    The pattern continues. The nth derivitive is
    ....................n
    ...................⎲
    f(x+nδ)/δ+ ⎳ n(-1)^k f(x+kδ)/δ
    ...................k=1

    The dots are there because the computer won't show spaces properly.

  • kodlu 2 years 43 weeks ago The second-moment method

    .. but I can't understand why "the proportion of x such that | f(x) - delta N | \geq (delta N / 2)" has delta N instead of delta^2 N which is the average value of f(x) as stated previously. And I haven't been able to turn inline commenting on in google chrome, my apologies.

  • olof 3 years 13 weeks ago Create an epsilon of room

    A few other articles had also been mysteriously truncated, but I have now restored them (and this one). If anyone spots another page that does not look right then please let us know, for example via the forums.

  • tao 3 years 14 weeks ago Create an epsilon of room

    For some strange reason, all revisions of this article have been truncated at the first paragraph, and I cannot find a way to retrieve any subsequent portion of the text. Has this also occurred for other articles? Is there any way to recover some copy of the full article?

  • tiptap 3 years 31 weeks ago Prove a consequence first

    That's a great explanation. Thanks.

  • tao 3 years 31 weeks ago Prove a consequence first

    f(n) is independent of n if the value of f(n) does not actually depend on n, i.e. it is constant as a function of n. For instance n-n is independent of n, as it is always 0.

    Equivalently, f(n) is independent of n if one has f(n)=f(m) for all n,m.

  • tiptap 3 years 31 weeks ago Prove a consequence first

    Proving the consequence first is a great way to simplify a problem.
    But I don't understand the example. What exactly does "independent" mean. How can f(n) be independent of n?

    Sorry if this is a stupid question, but I would really like to understand this.

  • FelixKlein 3 years 34 weeks ago To simplify a closed subset of the plane, approximate it using a grid of squares

    Suppose first that X is semialgebraic. Consider the function f :C—> R defined by

    f(z)= dist(z, X)

    Then for all but finitely many positive numbers t the level set C_t={ f=t} is a smooth curve. For t sufficiently small C_t will be a curve that contains X in its interior {f< t}. As an aside, for t small, the set {f\leq t} is homotopy equivalent to X.

    If X is not semialgebraic, then the pixellation Y that you constructed is compact, semialgebraic, contains X and is contained in D if the size of the squares is small enough. Now apply the previous construction to Y.

    PS My PhD student has been investigating approximations of planar sets by grids of squares (or pixellations). He has obtained quite interesting results. If P_r if the pixellation of a semialgebraic set with squares of size r then one can algorithmically associate to P_r a PL set S_r that in a rather strong sense to X as r–>0. In particular, many geometric invariants of S_r (such as area, perimeter, curvature measures, Betti numbers) converge to the corresponding invariants of X.

  • Sergio965 3 years 37 weeks ago To simplify a closed subset of the plane, approximate it using a grid of squares

    Isn't that always the case?

  • wlod 3 years 42 weeks ago How to use fixed point theorems

    There are good reasons to study not just the fixed point property (fpp) but the common generalization of fpp and the covering dimension theory, namely the universal functions, and even the universal (and couniversal) morphisms for general categories. (Since monoids are 1-object categories, one may also focus on the universal elements of monoids).

  • Ulagatin 3 years 43 weeks ago Functional analysis front page

    Hi,

    First of all, an excellent site! It's great to have such a compendium of mathematical knowledge online, accessable to all. So a great deal of thanks goes to the creators of this site!

    I'm in Year 12 in Australia and I just stumbled upon this page [on functional analysis], and I'd love to see it expanded. It looks to be an interesting field! I assume that capital Omega here is a space/topology, maybe even a set being integrated over? Could an explanation be given of the theory behind L^p(Omega) spaces and how it ties in more broadly to this topic?

    I look forward to hearing further (and just as a side-note, I believe my mathematical background to be good so far - I have a good understanding of convergence of sequences, Maclaurin series, complex numbers, derivatives of inverse trigonometric functions, etc). I have read a little of analysis, to which I have been impressed so far, but that I have only broadly skimmed.

    Thanks once again.
    Davin

  • thei 3 years 44 weeks ago Think axiomatically even about concrete objects

    I am sorry. I know that the definition is not *wrong* with a correct definition of set theory (which is usually not given in the books that use the above definition of ordered pair), so I reverted it. I just think that it is crazy to unnecessarily use that as definition, but it seems that many people love it.

  • ogerard 3 years 51 weeks ago To prove that a number is irrational, show that it is almost rational

    The use of this method for Zeta(3) is more involved but goes deeper into the principles of this method. I suggest that someone try to write up a description of this as Example 3.

  • ogerard 3 years 51 weeks ago Transform equation to reach a solved pattern

    This is indeed one instance of one of the most general method useful in mathematics and all the sciences. Z. A. Melzak has devoted a whole book to this idea : "Bypasses" (Wiley, 1983) showing how it encompasses geometry, algebra, analysis, physics, chemistry, information theory, technology in general.

    In this tricki entry, contributors have shown classical instances of how to find and build T (a transformation toward another form) motivated by the fact we know how to do U (the transformation/projection of the target form into needed information, here its solutions), mainly with algebraic objects.

    One of the most important aspect of this method or trick is that it can be nested at will.

  • winstonsmith 4 years 8 weeks ago To prove that a number is irrational, show that it is almost rational

    e+e^(-1) has sequence of approximations 2(1 + 1/2! + 1/4! + ... 1/(2n)!) and no immediately obvious (to me) formula for the continued-fraction expansion.

  • Anonymous (not verified) 4 years 9 weeks ago Mathematicians need to be metamathematicians

    "Think about the converse" should be added as a link in this article.

  • alex 4 years 11 weeks ago Bounding probabilities by expectations

    Here is a point which I feel needs to be emphasized more in Example 3.

    If we try to make the argument work without leaving \lambda to be optimized later, but by, say, initially setting \lambda=1, the argument will fail: we will get a useless bound. The reason: we need to pick a function F which will grow rapidly while E F(X) will grow slowly. In this case, E e^{X_1 + \ldots X_n} grows pretty fast with n.

    What kind of functions F work for this? Well, F(X)=X^2 works: out of the n^2 terms in (X_1 + \cdots + X_n)^2, almost all have expectation 0. Similarly, F(X)=X^{2k} works fine as well: in the sum (X_1 + \cdots + X_n)^{2k}, we will be able to easily cancel many terms because they have expectation 0.

    The central insight behind the proof in Example 3 is that picking F(x)=(1+t)^x for really, really small t works. The reason: the average of 1+t and 1/(1+t) is really close to 1. That is: near one, inversion is about the same as subtraction. This insight can be pushed a little further to argue that if X has mean 0, the quantity E (1+t)^X should be pretty close to 1. Thus one might hope that E[(1+t)^{X_1 + \cdots X_n}] = (E[(1+t)^{X_1}])^n grows slowly - after all, it is "approximately" 1^n = 1.

  • Anonymous (not verified) 4 years 18 weeks ago How to compute the (co)homology of a space

    Maybe it'd be nice to mention that if your space is being decomposed into U and V and these have non-empty intersection, then the end terms (H_0 and such) can be taken as reduced homology instead of just normal homology, simplifying some calculations.

  • Anonymous (not verified) 4 years 18 weeks ago How to compute the (co)homology of a space

    If I recall correctly, the Mayer-Vietoris sequence tells you something about a space decomposed as two sets _whose interiors cover the space_. So I think U and V must intersect in two intervals (which are homotopically trivial, so the rest of the proof runs the same).

  • Anonymous (not verified) 4 years 20 weeks ago How to solve cubic and quartic equations

    what is uv?