When is arccos a rational multiple of pi?

March 31, 2018 Leave a comment

Recently I had to test if the {\arccos} of some algebraic number is a rational multiple of {\pi} or not. I found this solution online and since it is quite nice, I write it here in a more generalized form.

Suppose that {r} is an algebraic number. Under which circumstances we have

\displaystyle \arccos(r) \in \pi\Bbb{Q}?

Suppose that {\arccos(r) = \frac{p}{q} \pi} with {p,q \in \Bbb{Z}, q > 0}. Then {q\arccos(r) = p\pi} and applying {\cos} we see that

\displaystyle \cos(q\arccos(r)) -(-1)^p = 0.

It is well known that the function {P_q\ :\ x \mapsto \cos(q\arccos(x))} is polynomial for {|x|\leq 1}. If we denote {f(x) = P_q(x)-(-1)^p} then {f} is a polynomial of degree {q} with leading coefficient {2^{q-1}}. Since we have {f(r) = 0}, the minimal polynomial {Q_r} associated to {r} must divide {f(r)}. This gives us the following necessary condition:

If {\arccos(r) \in \pi\Bbb{Q}} then there exist {p,q \in \Bbb{Z}}, {q > 0} such that {Q_r} (the minimal polynomial of {r}) divides {P_q\pm 1} (where {P_q} is the Chebyshev polynomial of degree {q}).

It is not difficult to see that this condition is also sufficient. Now, using this we have the following application:

Consequence. If {r} is an algebraic number whose minimal polynomial has a leading coefficient which is not a power of {2}, then

\displaystyle \arccos(r) \notin \pi \Bbb{Q}.

Since the minimal polynomial {Q_r} has a leading coefficient which is not a power of {2}, it cannot divide {P_q\pm 1} for some positive integer {q}. Therefore, following the arguments stated above, {\arccos(r) \notin \pi\Bbb{Q}}.

Applications.

  • {\arccos(\sqrt{n}/3)\notin \pi\Bbb{Q}} if {\gcd(n,3) \leq 3}.
  • {\arccos(\sqrt{m/n}) \notin \pi\Bbb{Q}} for {m,n \in \Bbb{N}^*} if {n>1},\ \gcd(m,n)=1 and {n} is not a power of {2}.
Advertisements

Romanian Masters in Mathematics contest – 2018

March 9, 2018 Leave a comment

Problem 1. Let {ABCD} be a cyclic quadrilateral an let {P} be a point on the side {AB.} The diagonals {AC} meets the segments {DP} at {Q.} The line through {P} parallel to {CD} mmets the extension of the side {CB} beyond {B} at {K.} The line through {Q} parallel to {BD} meets the extension of the side {CB} beyond {B} at {L.} Prove that the circumcircles of the triangles {BKP} and {CLQ} are tangent .

Problem 2. Determine whether there exist non-constant polynomials {P(x)} and {Q(x)} with real coefficients satisfying

\displaystyle P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20}.

Problem 3. Ann and Bob play a game on the edges of an infinite square grid, playing in turns. Ann plays the first move. A move consists of orienting any edge that has not yet been given an orientation. Bob wins if at any point a cycle has been created. Does Bob have a winning strategy?

Problem 4. Let {a,b,c,d} be positive integers such that {ad \neq bc} and {gcd(a,b,c,d)=1}. Let {S} be the set of values attained by {\gcd(an+b,cn+d)} as {n} runs through the positive integers. Show that {S} is the set of all positive divisors of some positive integer.

Problem 5. Let {n} be positive integer and fix {2n} distinct points on a circle. Determine the number of ways to connect the points with {n} arrows (oriented line segments) such that all of the following conditions hold:

  • each of the {2n} points is a startpoint or endpoint of an arrow;
  • no two arrows intersect;
  • there are no two arrows {\overrightarrow{AB}} and {\overrightarrow{CD}} such that {A}, {B}, {C} and {D} appear in clockwise order around the circle (not necessarily consecutively).

Problem 6. Fix a circle {\Gamma}, a line {\ell} to tangent {\Gamma}, and another circle {\Omega} disjoint from {\ell} such that {\Gamma} and {\Omega} lie on opposite sides of {\ell}. The tangents to {\Gamma} from a variable point {X} on {\Omega} meet {\ell} at {Y} and {Z}. Prove that, as {X} varies over {\Omega}, the circumcircle of {XYZ} is tangent to two fixed circles.

Source: Art of Problem Solving forums

Some quick ideas: For Problem 1 just consider the intersection of the circle {(BKP)} with the circle {(ABCD)}. You’ll notice immediately that this point belongs to the circle {(CLQ)}. Furthermore, there is a common tangent to the two circles at this point.

For Problem 2 we have {10\deg P = 21 \deg Q}. Eliminate the highest order term from both sides and look at the next one to get a contradiction.

Problem 4 becomes easy after noticing that if {q} divides {an+b} and {cn+d} then {q} divides {ad-bc}.

In Problem 5 try to prove that the choice of start points determines that of the endpoints. Then you have a simple combinatorial proof.

Problem 6 is interesting and official solutions use inversions. Those are quite nice, but it may be worthwhile to understand what happens in the non-inverted configuration.

I will come back to some of these problems in some future posts.

SEEMOUS 2018 – Problems

March 1, 2018 Leave a comment

Problem 1. Let {f:[0,1] \rightarrow (0,1)} be a Riemann integrable function. Show that

\displaystyle \frac{\displaystyle 2\int_0^1 xf^2(x) dx }{\displaystyle \int_0^1 (f^2(x)+1)dx }< \frac{\displaystyle \int_0^1 f^2(x) dx}{\displaystyle \int_0^1 f(x)dx}.

Problem 2. Let {m,n,p,q \geq 1} and let the matrices {A \in \mathcal M_{m,n}(\Bbb{R})}, {B \in \mathcal M_{n,p}(\Bbb{R})}, {C \in \mathcal M_{p,q}(\Bbb{R})}, {D \in \mathcal M_{q,m}(\Bbb{R})} be such that

\displaystyle A^t = BCD,\ B^t = CDA,\ C^t = DAB,\ D^t = ABC.

Prove that {(ABCD)^2 = ABCD}.

Problem 3. Let {A,B \in \mathcal M_{2018}(\Bbb{R})} such that {AB = BA} and {A^{2018} = B^{2018} = I}, where {I} is the identity matrix. Prove that if {\text{tr}(AB) = 2018} then {\text{tr}(A) = \text{tr}(B)}.

Problem 4. (a) Let {f: \Bbb{R} \rightarrow \Bbb{R}} be a polynomial function. Prove that

\displaystyle \int_0^\infty e^{-x} f(x) dx = f(0)+f'(0)+f''(0)+...

(b) Let {f} be a function which has a Taylor series expansion at {0} with radius of convergence {R=\infty}. Prove that if {\displaystyle \sum_{n=0}^\infty f^{(n)}(0)} converges absolutely then {\displaystyle \int_0^{\infty} e^{-x} f(x)dx} converges and

\displaystyle \sum_{n=0}^\infty f^{(n)}(0) = \int_0^\infty e^{-x} f(x).

Source: official site of SEEMOUS 2018 

Hints: 1. Just use 2f(x) \leq f^2(x)+1  and xf^2(x) < f^2(x). The strict inequality comes from the fact that the Riemann integral of strictly positive function cannot be equal to zero. This problem was too simple…

2. Use the fact that ABCD = AA^t, therefore ABCD is symmetric and positive definite. Next, notice that (ABCD)^3 = ABCDABCDABCD = D^tC^tB^tA^t = (ABCD)^t = ABCD. Notice that ABCD  is diagonalizable and has eigenvalues among -1,0,1. Since it is also positive definite, -1 cannot be an eigenvalue. This allows to conclude.

3. First note that the commutativity allows us to diagonalize A,B  using the same basis. Next, note that A,B both have eigenvalues of modulus one. Then the trace of AB is simply the sum \sum \lambda_i\mu_i where \lambda_i,\mu_i are eigenvalues of A and B, respectively. The fact that the trace equals 2018  and the triangle inequality shows that eigenvalues of A are a multiple of eigenvalues of B. Finish by observing that they have the same eigenvalues.

4. (a) Integrate by parts and use a recurrence. (b) Use (a) and the approximation of a continuous function by polynomials on compacts to conclude.

I’m not sure about what others think, but the problems of this year seemed a bit too straightforward.

Using parfor in Matlab

February 27, 2018 Leave a comment

We all know that loops don’t behave well in Matlab. Whenever it is possible to vectorize the code (i.e. use vectors and matrices to do simultaneous operations, instead of one at a time) significant speed-up is possible. However, there are complex tasks which cannot be vectorized and loops cannot be avoided. I recently needed to compute eigenvalues for some 10 million domains. Since the computations are independent, they could be run in parallel. Fortunately Matlab offers a simple way to do this, using parfor.

There are some basic rules one need to respect to use parfor efficiently:

  1. Don’t use parfor if vectorization is possible. If the task is not vectorizable and computations are independent, then parfor is the way to go.
  2. Variables used in each computation should not overlap between processors. This is for obvious reasons: if two processors try to change the same variable using different values, the computations will be meaningless in the end.
  3. You can use an array or cell to store the results given by each processor, with the restriction that processors should work on disjoint parts of the array, so there is no overlap.

The most restrictive requirement is the fact that one cannot use the same variables in the computations for different processors. In order to do this, the simplest way I found was to use a function for the body of the loop. When using a matlab function, all variables are local, so when running the same function in parallel, the variables won’t overlap, since they are local to each function.

So instead of doing something like

parfor i = 1:N
   commands ...
   array(i) = result
end

you can do the following:

parfor i=1:N
   array(i) = func(i);
end

function res = func(i)
   commands...

This should work very well and no conflict between variables will appear. Make sure to initialize the array before running the parfor, a classical Matlab speedup trick: array = zeros(1,N). Of course, you could have multiple outputs and the output array could be a matrix.

There is another trick to remember if the parpool cannot initialize. It seems that the parallel cluster doesn’t like all the things present in the path sometimes. Before running parfor try the commands

c = parcluster('local');
c.parpool

If you recieve an error, then run

restoredefaultpath
c = parcluster('local');
c.parpool

and add to path just the right folders for your code to work.

Regular tetrahedron – computing various quantities in terms of the side-length

February 2, 2018 Leave a comment

Sometimes one needs to find certain quantities related to the regular tetrahedron in {\Bbb{R}^3}, like volume, radius of the circumscribed sphere, radius of inscribed sphere, distance between opposite sides, etc. in terms of the side-length which we’ll note in the following with {a}. In the past I needed to find the angle under which every side is seen when looking from the center of the regular tetrahedron.

Here’s a trick which can help you find rather easily everything you need related to the regular tetrahedron: just embed it into a cube. We can see rather easily that when drawing certain diagonals of the faces of a cube, like in the figure below, we can recover a regular tetrahedron. Now it becomes rather easy to solve all questions above. We note that the ratio between the side of the cube (denoted by {\ell}) and the side of the embedded tetrahedron (denoted by {a}) is {\sqrt{2}}: {a = \ell \sqrt{2}}.

tetra_cube_1

Here are a few ideas:

1. Finding the volume of the tetrahedron in terms of its sides.

The volume of the cube is {\ell^3}. The volume of the tetrahedron can be obtained by cutting four corner pyramids with volumes {\ell^3/6} (recall that volume of a pyramid is (area of base) {\times} (height) {/3}). Therefore the volume of the regular tetrahedron is {2\ell^3/6 = l^3/3}. Replacing {\ell = a/\sqrt{2} } we get that the volume of the tetrahedron is {a^3/(6\sqrt{2})}.

2. Finding the circumradius {R}.

It is not difficult to see that the sphere passing through the vertices of the tetrahedron also passes through the vertices of the cube. Therefore its radius is a long diagonal of the cube divided by {2}. This gives {\ell \sqrt{3}/2}. Replacing {\ell=a/\sqrt{2}} we get that the circumradius is {R = a\sqrt{6}/4}.

3. Finding the inradius {r}.

Once we have the volume and the circumradius, finding the inradius is not that difficult, since the symmetry of the figure shows that {r+R = h}, where {h} is the distance from a vertex to the opposite face, also called the height. We can find the height from the formula of the volume (recalled above), and then find {r = h-R}. Also note that since the center of the tetrahedron is also the centroid, we must have {R=3r}, so we have another quick finish solution.

However, let’s use the cube to do this. We can choose a system of coordinates putting the origin at the center of the cube (and tetrahedron). Put the cube so that its vertices have coordinates {\pm \ell/2,\pm \ell/2,\pm \ell/2} and suppose that the tetrahedron corresponds to the vertices {A(\ell/2,\ell/2,\ell/2)}, {B(-\ell/2,-\ell/2,\ell/2)}, {C(\ell/2,-\ell/2,-\ell/2)}, {D(-\ell/2,\ell/2,-\ell/2)}. All we need to do is to compute the distance from the origin to the plane {(BCD)}. This is immediate if we know the equation of this plane. Fortunately, it is really easy to see that the coordinates of {B,C,D} verify {x+y+z+\ell/2 = 0} (if not, then note that the normal to {(B,C,D)} is the vector {(1,1,1)} and figure out the remaining translation constant). We know that if a plane is defined by the equation {ax+by+cz+d=0} then the distance from {(x_0,y_0,z_0)} to this plane is

\displaystyle \frac{|ax_0+by_0+cz_0+d|}{\sqrt{a^2+b^2+c^2}}.

Apply this to our problem and the distance from the origin to {(BCD)} becomes {\ell/(2\sqrt{3})}. Replace {\ell = a/\sqrt{2}} and we get {r = a/(2\sqrt{6})=a\sqrt{6}/12}.

4. Find distance between opposite sides.

This is particularly easy with the cube. The distance between the opposite sides is exactly the distance between two parallel faces of the cube and that is {\ell = a/\sqrt{2}}.

5. Find angle made by two rays connecting the center with vertices.

Use the coordinate system introduced in 3. and just compute the angle between vectors {\vec u = (\ell,\ell,\ell)} and {\vec v = (-\ell,-\ell,\ell)}, for example. If {\alpha} is the angle between {\vec u} and {\vec v} we get that

\displaystyle \cos \alpha = \frac{\langle \vec u,\vec v\rangle}{\|\vec u\| \|\vec v\|}=\frac{-\ell^2}{3\ell^2} = -\frac{1}{3}.

Therefore {\alpha = \arccos (-1/3)}.

Plotting 3D level sets in Paraview

December 30, 2017 1 comment

Surfaces can be represented as certain level-sets for some 3D functions. Given a set of points with values attached to them a level set associated to a certain number will separate the points into two sets: with values higher or lower than the number considered. It is nice to have good looking plots when working with the level-set method in shape optimization. Paraview is a nice, open source framework, which has the right tools in order to produce high quality plots.

I’ll briefly describe below how to use Paraview to make some nice pictures of level-sets. First of all, you’ll need your data in some format that Paraview can understand. I use vtk file format for which there is a nice automated interface in the software I use for the optimization (FreeFem++). In the vtk file you need to have a set of points and a scalar value attached to them.

If you want to create level-sets associated to certain values, follow the steps below:

    1. Load your file (containing points with at least a scalar value) and click Apply.
    2. Next, go to Filters/Alphabetical and select “Cell Data to Point Data” (if you forget to do this, you’ll get a rough surface where you see the discretization). Click Apply.
    3. Then apply the Contour filter (by clicking the button or going in Filters/Alphabetical). You’ll have to select the field for which the contours will be drawn and then put in the values of the level-sets you want to see. Click Apply. An example can be seen below.lvlview

If your level-set cuts the boundary of the domain, Paraview will draw a hole there. If you want to have a closed region instead, you need to use the IsoVolume filter instead of the Contour one. The difference is that you need to specify two values and Paraview will draw the surface enclosing the points corresponding to these values. Many other features are directly available: you can color the level set following another scalar value, you can set the lighting, etc. You can also symmetrize your geometry using the Reflect filter. Below you can see a result built from my work.

chSuppfix

You can also create animations in a pretty  straightforward way. Just go to View and select the Animation box. Then you’ll see the animation options. Add a Camera object with Orbit field selected. You’ll be presented with multiple options, like the center of rotation, direction of the vertical and initial position. Once everything is set, click the play button to see the animation. Then go to File/Save Animation to save it to a file.

 

I heard that Paraview could to many things when dealing with visualization aspects, but I hesitated to use it until now since the interface is not straightforward. The use of Filters is not clear in the beginning, but after playing with some examples, everything becomes really easy to use. The next step is to automatize all this using scripts.

Happy New Year!

Putnam 2017 A3 – Solution

December 4, 2017 Leave a comment

Problem A3. Denote {\phi = f-g}. Then {\phi} is continuous and {\int_a^b \phi = 0}. We can see that

\displaystyle I_{n+1}-I_n = \int_a^b (f/g)^n \phi = \int_{\phi\geq 0} (f/g)^n \phi+ \int_{\phi<0} (f/g)^n \phi

Now note that on {\{ \phi>=0\}} we have {f/g \geq 1} so {(f/g)^n \phi \geq \phi}. Furthermore, on {\{\phi<0\}} we have {(f/g)^n <1} so multiplying with {\phi<0} we get {(f/g)^n \phi \geq \phi}. Therefore

\displaystyle I_{n+1}-I_n \geq \int_{\phi \geq 0} \phi + \int_{\phi<0} \phi = \int \phi = 0.

To prove that {I_n} goes to {+\infty} we can still work with {I_{n+1}-I_n}. Note that the negative part cannot get too big:

\displaystyle \left|\int_{ \phi <0 } (f/g)^n \phi \right| \leq \int_{\phi<0} |\phi| \leq \int_a^b |f-g|.

As for the positive part, taking {0<\varepsilon< \max_{[a,b]} \phi} we have

\displaystyle \int_{\phi\geq 0} (f/g)^n \phi \geq \int_{\phi>\varepsilon}(f/g)^n \varepsilon.

Next, note that on {\{ \phi \geq \varepsilon\}}

\displaystyle \frac{f}{g} = \frac{g+\phi}{g} \geq \frac{g+ \varepsilon}{g}.

We would need that the last term be larger than {1+\delta}. This is equivalent to {g\delta <\varepsilon}. Since {g} is continuous on {[a,b]}, it is bounded above, so some delta small enough exists in order for this to work.

Grouping all of the above we get that

\displaystyle I_{n+1}-I_n \geq \int_{\phi \geq 0} (f/g)^n \phi \geq \int_{\phi>\varepsilon} \varepsilon (1+\delta)^n.

Since {|\phi>\varepsilon|>0} we get that {I_{n+1}-I_n} goes to {+\infty}.

%d bloggers like this: