Lab 5: A second adventure

Once again, you will choose your own adventure for this lab. But this time your final product will be a group presentation instead of a formal article. The presentations will be graded in the same way as the articles, except that the “exposition” category will be replaced with a “presentation” category. Follow the jump for the fine print. Continue reading

Numerical Integration: Summary and Conclusions

In this lab we looked at some various methods to compute integrals.
Those methods were, Riemann Sums: left rectangle, midpoint, and right rectangle, Trapezoidal, and Simpsons Rule.

We tested various methods and got results that showed that Simpsons Rule was very accurate, in many cases exact for cubic functions. We explored this more saw that Simpsons rule and the actual integration yielded the same result. This was also a proof of our conjectures about this method Finally we showed where the Simpsons Rule came from.

Now with all of that there are many other things that can be explored. Exploring more functions than cubics, (trig functions, logarithmic, exponential, etc.) and seeing which methods work best for those. Other routes one might take would be to explore higher dimensions. Some questions that could be explored would be how to test the accuracy for functions that don’t have an antiderivative? What methods would seem to work best? How small of an interval would be needed?

Equation for Simpsons Rule: Proof and Derivation

We get in the book that an equation for a parabola for any three points is

$ q(x)=A\frac {(x-b)(x-c)}{(a-b)(a-c)}+ B \frac{(x-a)(x-c)}{(b-a)(b-c)} +C\frac{(x-a)(x-b)}{(c-a)(c-b)}$

This is the formula for some parabola $ q= mx^2+nx+p$ through the points, (a, A), (b,B), (c,C), we will take this as a given and go from there.

First we need to say we are working on a interval [-h, h]. Then our three points will be (-h, f(-h)), (0,f(0)), (h,f(h)).

Photo on 2013-11-18 at 09.09

First we write a generic equation for this quadratic. We can do this using the formula given and replacing the values:
$ q(x)=f(-h)\frac {(x)(x-h)}{(-h)(-2h)}+ f(0) \frac{(x+h)(x-h)}{(h)(-h)} +f(h)\frac{(x+h)(x)}{(2h)(h)}$

Reducing this we get:

$ q(x)=f(-h)\frac {x^2-xh}{2h^2}+ f(0) \frac{(x^2-h^2)}{-h^2} +f(h)\frac{x^2+xh}{2h^2}$

Now we integrate from [-h, h].

Photo on 2013-11-18 at 09.20

$\int^h_{-h} f(-h)\frac {x^2-xh}{2h^2}+ \int^h_{-h} f(0) \frac{(x^2-h^2)}{-h^2} +\int^h_{-h} f(h)\frac{x^2+xh}{2h^2}$

$=f(-h) (\frac{x^3}{6h^2} – \frac{x^2}{4h}) |_{-h}^h + f(0) (\frac{x^3}{-h^2} + x) |_{-h}^h + f(h) (\frac{x^3}{6h^2} + \frac{x^2}{4h}) |_{-h}^h$

Just taking the first integral:

$f(-h)((\frac{h^3}{6h^2} – \frac{h^2}{4h})-(\frac{-h^3}{6h^2} – \frac{h^2}{4h}))$

$=f(-h)\frac{h}{3}$

Evaluating the other integrals and reducing we get

$ f(0)\frac{4}{3}h$ and $f(h)\frac{h}{3}$

So we have: $f(-h)\frac{h}{3} + f(0)\frac{4}{3}h +f(h)\frac{h}{3}$
$=\frac{h}{3}[f(-h)+4f(0)+f(h)]$

Now the points if you change the points we were working with to

$(x_{i-1},f(x_{i-1})),(x_i,f(x_{i})), (x_{i+1},f(x_{i+1}))$

we get
$=\frac{h}{3}[f(x_{i-1})+4f(x_{i})+f(x_{i+1})]$

This is the formula for Simpson’s Rule. This has major implications. It shoes how accurate it can be. This is accurate because when you have three points and a function that goes through them Simpsons rule finds a best fit quadratic for that region. Then we see that the formula does not depend on the actual equations themselves, but the points that one is evaluating them at and the interval they are going across.

Congruent mod 4 primes

One of the last sections in our primes lab had to do with an interesting distribution of primes that are congruent to 1 and 3 mod 4. This means that our prime number, n, is congruent to either 1 (mod 4) or 3 (mod 4). We can divide these up into two sets of primes numbers:

$\pi_1(n)$= #{primes p| p $\leq$ n and p = 1 + 4k, for some positive integer k}

$\pi_3(n)$= #{primes p| p $\leq$ n and p = 3 + 4k, for some positive integer k}

So the question is, how many primes actually fit into these two sets?

 

n

$\pi(n)$

$\pi_1(n)$

$\pi_3(n)$

$\pi_1(n)$/$\pi(n)$

$\pi_3(n)$/$\pi(n)$

10

5

1

1

.2

.2

25

9

3

4

.33

.44

50

15

6

7

.4

.47

100

26

11

12

.42

.46

1000

168

80

86

.48

.51

10000

1229

609

618

.5

.5

100000

9592

4783

4807

.5

.5

As we can see, as our n approaches infinity, the two sets comprise together roughly 100% of the primes. There are some primes missing, as evidenced with n is small. 2 is a good example of one that doesn’t work with this relationship. But, as we can see, when n gets really large, the relationship holds really well.

Through this, we can make an extension of our very first proof, where we found that there are an infinite number of primes.

Let’s prove: If $\pi(n) \geq \pi_1(n) + \pi_3(n)$, then as n approaches infinity, $\pi_1$ and $\pi_3$ are infinite sets.

We already know that $\pi(n)$ is an infinite set, so our question is whether $\pi_1(n)$ and/or $\pi_3(n)$ are also infinite. As n approached infinity, $pi_1(n) \approx 0.5\pi(n)$, and $pi_3(n) \approx 0.5\pi(n)$. So, we can plug in our values: $\pi(n) \geq 0.5\pi(n) + 0.5\pi(n)$, and since $\pi(n)$ is an infinite sets, it is the sum of two infinite sets. So, as n approaches infinity, $\pi_1$ and $\pi_3$ also approach infinity, so they are also infinite sets. This is what we wanted to prove in the first place, so we are done.

The p-adic Numbers

Previously, we discussed the absolute values on $Q$, the real numbers, Cauchy sequence, and basic process of computing the p-adic representation of a number. Now, we move ahead and discuss how to construct these p-adic numbers. We do this by using the absolute value in the usual sense as to how it is used with the reals.

$Definition$. The field of p-adic numbers $Q_p$ is defined to be the set of all equivalence classes of p-adic Cauchy sequence.

As mentioned earlier, we can represent p-adic numbers using the Cauchy sequence. With the given definition, now we know that for any p-adic Cauchy sequence, the sequence converges to a p-adic number. Natural question to arise would be to ask *how*. To address this *how* and to convince ourselves, we will consider a quick example before generalizing it.

Let’s take the 3-adic representation of $241$. We surly know that $241$ is a Cauchy sequence that converges to $241$ for {$241$, $241$, $241$, $…$} . The 3-adic representation of $241$ is $1 + 2*3^1 + 2*3^2 + 2*3^3 + 2*3^4$ or $(1, 2, 2, 2)$. This expansion represents the class of all Cauchy sequence equivalent to {$1$, $1+2*3^1$, ${1+2*3^1 + 2*3^3}$, $…$}. Looking closely, we notice the sequence as follows {$3$, $3^2$, $3^3$, $…$}. Taking the limit, we see that $lim_{n\to\infty}$ $3^n = 0$ for 3-adics. How? As we recall from absolute values of $Q$ for any prime $p$, we write $|p^0*k|=1$, $|p*k|=p^{-1}$, $|p^2*k|=p^{-2}$ and $|p^n*k|=p^{-n}$ in general for some constant $k$ as $n\to \infty$. It would make intuitive sense for $|3^n|=3^{-n}$ to approach zero as $n\to \infty$ because of the inverse. Let’s note the existence of the inverse relation we see here with the p-adic numbers. As $3^n$ grows without bounds, its 3-adic representation converges to zero.

Looking at the general case of p-adic Cauchy sequence, we see that any number in its p-adic representation will converge to zero and can be written as

{$a_n$} = {$a_0 * p^0, a_0 * p^0 + a_1*p^1, … , a_0 * p^0 + a_1*p^1 + a_2*p^2 + … + a_n*p^n$}

where $a_0, a_1, …, a_n$ represent the coefficients.  This p-adic expansion for the Cauchy sequence is abbreviated in the form of $a_0.a_1a_2a_{3,…,p}$. So, the 3-adic representation for $241$ can be abbreviated as $1.22\bar{2}_3$ where $0 \leq a_i \leq p-1$.

Now that we have a general knowledge of how the p-adic numbers work and how it’s constructed, we will consider another interesting representation of negative integers with p-adics. Let’s consider the p-adic expansion of $-1$ for any $p$. To start with, we begin by considering the 5-adic expansion for it.

Solution to $x + 1 = 0$ $mod$ $5$ $is$ $x = 4 = 4*5^0$

Solution to $x + 1 = 0$ $mod$ $5^2$ is $x = 24 = 4*5^0 + 4*5^1$

Solution to $x + 1 = 0$ $mod$ $5^3$ is $x = 124 = 4*5^0 + 4*5^1 + 4*5^2$

.

.

Solution to $x + 1 = 0$ $mod$ $5^n$ is $x = 4*5^0 + 4*5^1 + 4*5^2 + … + 4*5^{(n-1)}$

Next, we consider the *7-adic* expansion of $-1$.

Solution to $x + 1 = 0$ $mod$ $7$ is $x = 6 = 6*7^0$

Solution to $x + 1 = 0$ $mod$ $7^2$ is $x = 48 = 6*7^0 + 6*7^1$

Solution to $x + 1 = 0$ $mod$ $7^3$ is $x = 342 = 6*7^0 + 6*7^1 + 6*7^2$

.

.

Solution to $x + 1 = 0$ $mod$ $7^n$ is $x = 6*7^0 + 6*7^1 + 6*7^2 + … + 6*7^{(n-1)}$

$Conjecture$. The *p-adic* expansion of $-1$ for any $p$ is represented as $(p-1, p-1, p-1, …)$.

 

Numerical Integration- Simpson’s Rule

If you’ve kept up on recent blog posts, you’ll notice that in our data one method for integration seemed to work without any error. This method was Simpson’s Rule. This fact sparked our interest as to why does this method work so well? In particular, we noticed that it was almost flawless with cubic functions. Why is this? From the text, we were given the idea to algebraically compute Simpson’s rule approximation and compare it to the actual integral of the special case in which our interval is [-h,h] and n, our number of rectangles, being 2 for $f(x)=ax^{3}+bx^{2}+cx+d$.

We began by computing the actual integration:

$\int\limits_{-h}^{h} (ax^{3}+bx^{2}+cx+d) dx$ $\implies$ ($\frac{ax^{4}}{4}$ + $\frac{bx^{3}}{3}$ + $\frac{cx^{2}}{2}$ + $dx$ + $C$)|$^{h}_{-h}$

[$\frac{ah^{4}}{4}$ + $\frac{bh^{3}}{3}$ + $\frac{ch^{2}}{2}$ + $dh$ + $C$]-[$\frac{a(-h)^{4}}{4}$ + $\frac{b(-h)^{3}}{3}$ + $\frac{c(-h)^{2}}{2}$ + $d(-h)$ + $C$]

$= \frac{2bh^{3}}{3} + 2dh$

The equation for Simpson’s Rule is $\frac{1}{3}[f(x_{i-1})+4f(x_{i})+f(x_{i+1})]h$

In using two rectangles we get: $\frac{h}{3}[f(-h)+4f(0)+f(h)]$ $\implies$ $\frac{h}{3}[(a(-h)^{3}+b(-h)^{2}+c(-h)+d)+4d+(a(h)^{3}+b(h)^{2}+c(h)+d)]$

$= \frac{h}{3}(2bh^{2}+6d)= \frac{2bh^{3}}{3} + 2dh$

And thus we find that in cubic functions Simpson’s rule is the most accurate method for computing the integration.

For further research we can look at what happens when we change the bounds to [a,b]. We can also calculate the actual integral and the Simpson’s rule for different types of functions too see if this method really holds up as being the most accurate method for numerical integration.

 

The Real Numbers and the Cauchy Sequence

To further continue with our path into studying the p-acid numbers, we must be able to construct it to have a deeper understanding of it. In order to do so, we break from learning the properties and how the p-adic numbers work. Instead we will take time to observe what a Cauchy sequence is and it’s relation to the p-adics. Continuing on, we will first define the limits of the Cauchy sequence of the rational numbers.

$Definition$. For a given sequence of rational numbers ${a_n} = ({a_1, a_2,…})$, it is known as being real Cauchy sequence if for some $ε > 0$ , there exists a positive integer $N$ such that for all $i,j>N, |a_i-a_j|_{\infty} < ε$.

Let’s consider the following real number $1.4142135…$. We can represent it by the limit of the sequence as

$a_1 = 1 = 1*10^0$

$a_2 = 1.4 = 1*10^0 + 4*10^{-1}$

$a_3 = 1.41 = 1*10^0 + 4*10^{-1} + 1*10^{-2}$

$a_4 = 1.414 = 1*10^0 + 4*10^{-1} + 1*10^{-2} + 4*10^{-3}$

$…$

Can the reader recognize the sequence? The expansion of $1.4142135…$ is the converging Cauchy sequence representation of the constant $\sqrt{2}$. This sequence can also be written as $({1, 1.4, 1.41, 1.414, 1.4142, …})$. To be completely sure that $\sqrt{2}$ is a Cauchy sequence, next we set $ε = 0.05$. We see that $N = 2$ and verify this by computing $|1.41-1.414|_{\infty} = 0.004 < 0.05 = ε$ which is true.

If we are given two real Cauchy sequences ${a_n}$ and ${b_n}$, we know that the both of the sequences represent the same real number if ${|a_n – b_n|}$ converge to 0. This is fairly easy to demonstrate and see. Taking ${a_n} = ({1, 1, 1, 1, 1, …})$ and ${b_n} = ({0.9, 0.99, 0.999, 0.9999, 0.99999, …})$ as an example, we see that ${|a_n – b_n|} = ({0.1, 0.01, 0.001, 0.0001, 0.00001, …})$ converges to 0 as $n\rightarrow{\infty}$ . The Cauchy sequence here for ${a_n}$ can seem counter intuitive at first if the reader is countering such case for the first time. After all, how can $0.999\bar{9} = 1$ be true? To clearly understand $how$ this works, we observe the sum of the infinite series for $0.999\bar{9}$.

$$0.999\bar{9} = lim_{n\rightarrow\infty} 9 \frac{1}{10} + 9\frac{1}{100} + 9\frac{1}{1000} + … + 9\frac{1}{10^n}$$

Now we apply the geometric sum given by

$$1 + r + r^2 + … + r^{n-1} = \frac{1 – r^n}{1 – r}$$

to our sequence to get

$$  = \frac{9 *(1/10)}{1- \frac{1}{10}} = \frac{9*10}{10*9} = 1$$

Our $r$ value here is $1/10$ because that is our common ratio. As we can see, it is true that $0.999\bar{9}=1$ for the sequence of $0.999\bar{9}$. Note that this is true because we consider the *infinite* sequence of $0.999\bar{9}$. If we did have a cutoff, then we could say that $0.9999$ is approximately equal to $1$ with a slight error. But that’s clearly not the case here.

Now that we have observed the Cauchy sequences of rational numbers, we will next study the p-adic numbers and how we construct it with our thus far accumulated knowledge regarding absolute value and the Cauchy sequence.

 

Absolute values on Q (Part II)

Continuing on from absolute values on Q part I/ , I am going to show that the definition of p-adic absolute value satisfies the three properties of absolute values.

Property 1

Let $x=0$ and p be a fixed prime.  By definition then, $|x|_p = 0$.  This satisfies the first property ($|x|_p=0$ if and only if $x=0$).

Suppose now $x \ne 0$.  Then $|x|_p = p^{-ord_p(x)}$.  Using Conjecture 1, $|x|_p=|p^n \cdot a|_p =p^{-n}$.  Since $p^{-n}$ cannot be 0, $p^{-n} > 0$.

Property 2

Let $x=0$ and $y \ne 0$ and p be a fixed prime.  Then $|x \cdot y|_p = |0|_p = 0 = |x|_p \cdot |y|_p$.

Suppose $|x|_p = |p^n \cdot a|$ and $|y|_p = |p^n \cdot b|$.  In other words, x and y have the same exponent on p. Then, by definition,

$|x \cdot y|_p = |p^n \cdot a \cdot p^n \cdot b|_p = |p^{2n} \cdot ab|_p = p^{-2n}$.

By the second property,

$|x \cdot y|_p = |x|_p \cdot |y|_p = |p^n c\dot a|_p \cdot |p^n \cdot b|_p = p^{-n}p{-n}=p{-2n}$

Suppose x and y have different exponents on the p.  $|x|_p=|p^n \cdot a|_p and |y|_p=|p^m cdot b|$.  Multiply x by y….

$|xy|_p=|p^n \cdot a \cdot p^m \cdot b|_p=|p^{n+m} \cdot ab|_p=p^{-n-m}$

By the second property,

$|xy|_p=|x|_p \cdot |y|_p = p^{-n} \cdot p^{-m}=p^{-n-m}$.

Property 3

Let $x=y=0$ and p be a fixed prime.  Then by definition $|x+y|_p = 0$.  This partly satisfies the property for $0 \le 0+0$  Now consider $x \ne 0$.  Then $|x+y|_p = |x|_p = |p^n \cdot a|_p = p^{-n}$.    This contributes to satisfying the property for $p^{-n} \le p^{-n} + 0$.

Now let x and y have the same exponent on p.

$|x+y|_p = |p^n \cdot a + p^n \cdot b|_p = |p^n(a+b)|_p=p^{-n}$

If the definition satisfies the property, then $p^{-n}$ should be less than $|x|_p+|y|_p$.  In fact this is true because $|x|_p+|y|_p = p^{-n}+p^{-n}$ which is larger than $p^{-n}$.

Last case is when x and y have different exponents on p.

$|x+y|_p=|p^n \cdot a + p^m \cdot b|_p=p^{-n}$ where $n<m$

Now consider property 3.

$|x|_p+|y|_p=p^{-n}+p^{-m}$

Now that p-adic absolute values do satisfy the properties of absolute values, there is one more thing to look at:  Archimedean absolute values.  A little warning for you, the following definition is counter-intuitive.

Definition 2:  An absolute value on Q is said to be non-Archimedean if the properties of absolute values are satisfied along with an additional property:

$|x+y| \le max(|x|,|y|)$ for all x,y \in Q.

Absolute values that satisfy the three properties but not the fourth are said to be Archimedean.

Theorem 1:  p-adic absolute values are non-Archimedean.

It has already been shown that p-adic absolute values satisfy the first three conditions.  Now all that needs to be shown is that p-adic absolute values satisfy the fourth property.  Assume p is a fixed prime

Case 1: $x=y=0$

     $|x+y|_p = |0|_p = 0    \le        max(|x|_p,|y|_p) = 0$

 Case 2: $x \ne 0, y=0$

    $|x+y|_p = |x|_p = p^{-n}     \le     max(|x|_p,|y|_p) =  max(p^{-n}, 0) = p^{-n}$

Case 3:  x and y have the same exponent on p

     $|x+y|_p = p^{-n}             \le                max(|x|_p,|y|_p) = max(p^{-n}, p^{-n}) = p^{-n}$

Case 4:  x and y have different exponents on p (n<m)

    $|x+y|_p = p^{-n}              \le               max(|x|_p,|y|_p) = max(p^{-n}, p^{-m}) = p^{-m}$

QED

Polyhedra: Truncations

Truncation is the act of cutting the corners from the faces of a shape around its vertices. When truncating a regular polyhedron, each vertex will create a new face. This new face will have the same amount of edges as the number of faces meeting at the vertex. Therefore, when truncating a tetrahedron which has three triangle meeting at each of its vertices, a new triangle is formed at the vertex.

Now, what happens when a regular polyhedron is truncated to the point where there are no edges from the original shape? In this case, the only edges of the original shape would be of those that were cut form the corners. The number of faces on the new shape would therefore be dependent on the number of vertices on the old shape. A tetrahedron, for example, has four vertices. Therefore, the new shape would have four faces. These faces, as mentioned previously, would be triangles. However, notice that the tetrahedron has four triangular faces already. Therefore, a fully truncated tetrahedron produces a new tetrahedron!

tetra1tetra2tetra3tetra4

Next we will explore what happens when we truncate a cube. As stated before, the number of faces will be dependent on the number of vertices. With a cube, there are eight vertices. After we truncate the cube to the point where there are no more faces of the regular shape, we should expect to see a new polyhedron with eight faces. These new faces would have the shape of a triangle. Our new polyhedron will be an octahedron. We see a relation between these two polyhedra. The octahedron has eight faces and six vertices, and the cube has six faces and eight vertices. Both of these polyhedra when truncated completely will create one another.

cube1cube2cube3cube4

The final two regular polyhedra are the dodecahedron and the icosahedron. It follows the same formula as before with relation to the vertices and faces. Once you truncate the dodecahedron completely it ends up as the icosahedron. Similar to the cube and octahedron, the icosahedron truncates fully to the dodecahedron.

This is the truncation of the dodecahedron to the icosahedron:

dode1dode2dode3dode4dode5

 

If you need a visual on these shapes truncating, the site http://www.vandeveen.nl/Wiskunde/Diversen/Archimedean.html can be very useful.\

With all of our regular polyhedra, we see that when you truncate them completely you will end up with another regular polyhedra. The tetrahedra truncates to another tetrahedra. A cube to an octahedron and vice versa. Finally, the dodecahedron will truncate completely into the icosahedron and, similar to the cube and octahedron, the icosahedron truncates to the dodecahedron.