Tricki
a repository of mathematical know-how

Recent comments

  • eddingtonross If you are calculating an integral, complex substitutions are not forbidden

    I don't think this statement is true, nor the consequence immediately obvious given it (otherwise we could apply the same sort of argument to \sin(x) for instance).

    Parameterizing the arc as Re^{it} for t \in [0, \pi/4], the integral over the arc is \int_0^{\pi/4}e^{iR^2e^{2it}}(iRe^{it}dt).

    Expanding with Euler's Formula gives R \int_0^{\pi/4} \left(i \cos(t + R^2 \cos 2t) - \sin(t + R^2 \cos 2t) \right) e^{-R^2 \sin 2t} dt.

    Both the real and imaginary integrands are bounded above in absolute value by Re^{-2R^2t}, which means the integrals are bounded above by {(1-e^{\pi R^2/4}) \over 2R} \leq {1 \over 2R} and so the contribution from the arc does vanish at infinity.

  • Fedor Petrov Dimension arguments in combinatorics

    Why do we need \mathbb{R} instead \mathbb{F}_2 in the proof of Sauer-Shelah lemma? It looks that any field would work.

  • arrow Bijections and counting

    The image of each X_i ought to be {-1, 1}, I think.

  • luke Geometric view of Hölder's inequality

    I am not quite sure where to put this article. There is a 'use convexity' link in the 'estimating integrals' section but also one for Hölder's inequality.
    I guess the best would be a link from both articles (if they exist one day) to this one?

  • Valerius Use integration by parts to exploit cancellation

    Is there an analogue of this trick for the multidimensional Fourier transform?

  • Gurmeet 7 years 36 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__ 8 years 8 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 8 years 25 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 8 years 25 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__ 8 years 35 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 9 years 10 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 9 years 10 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 9 years 32 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 9 years 33 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 9 years 49 weeks ago Prove a consequence first

    That's a great explanation. Thanks.

  • tao 9 years 50 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 9 years 50 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 10 years 1 week 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 10 years 3 weeks ago To simplify a closed subset of the plane, approximate it using a grid of squares

    Isn't that always the case?

  • wlod 10 years 9 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 10 years 9 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 10 years 11 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 10 years 17 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 10 years 17 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 10 years 27 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.