Elaboration on two known issues in the context of finding an automated approach

Each post marked with “known” in the title is about the known results and concerns my notes, many of the notes are not thoroughly checked and the solutions are non-rigorous. In this post, we are going to start with the problems, have informal look a these as well as the surroundings of the problems and then try to elaborate on a potentially interesting direction in problem solving. The key point would be to use multi-variable approach, ie. the conversion of the variables of the original task to a multivariable task, then introduce strategies that would just take advantage of contraction search and then involve 2nd price auction problem solvers bidding for their chance, which would finally lead to more structured problem solving. This post is very informal and remains part of my internal analysis of certain problems and the reader might find it difficult to read.

cos1 irrational

As many of you know the answer to the problem, I will make a short introduction as how to handle problems in a generic way. What we currently know is that we will be dealing with a function. Will we be analyzing its values or only one value? We will be analyzing its values in general unless we notice something special about the given value for an argument equal to 1. Here, we are dealing with a known function and students know that the cosine function has also irrational values. Assuming that we will not pursue the path claiming that argument 1 is in some way special, we will focus on taking a closer look at more values of the cosine function.

Knowing that will focus on more values of the cosine function, lets think what to do next. Here we have the case that we know much about the function itself, in generic cases that is not the case and we should learn more about the function. That is indeed the very first thing as might show us that, for instance, argument 1 is a special case. Here, we don’t claim it.

As we know that cosine function has irrational values, we might try to build a chain of implications based on the character of the cosine function to connect cos1 with cos30, value of which is irrational. If that were possible, we could be able to prove the task.

Let us now assume that \cos 1 be rational as we know that . From the character of the cosine function we have that \cos(2x)=2\cos(x)^2-1, which leads to a conclusion that cos2 is also rational. Knowing that \cos (n+1)+\cos (n-1)=2\cos n\cos 1, we will see that for n=2 we could find a rational value of cos3. Iterating that, we could find a rational value of cos30, which leads to contradiction, making our claim false, q.e.d.

What we managed to do was to find the chain of implications based on the character of the cosine function to show that if rationality of cos1 depends on rationality of cos30. But, why did we choose this solution?

Lets take a closer look at the problem again. We have a special case. If we don’t say it is special indeed, we must know how to connect values of cos30 and cos1. In the same time, we don’t know if cos1,cos2,…,cos89 are rational or not. If we were not able to connect these two values, we would have to find something special about cos1.

Reductio ad absurdum, as is, is an assumption of the opposite so what matters is using it is to find the place where the logical chain leads to contradiction with the very assumption. So, before diving into the line of the proof, we need to be able to tell how we could be able to find the contradiction.

A good example of this is a proof of irrationality of \pi or e. In the first proof, (for the sake of contradiction) we assumme \pi =\frac{p}{q}, , where p, q are comprime integers. And then we consider I_n =\int_0^{p/q}\frac{x^n(p-qx)^n}{n!}\sin x dx, n\in N , showing that I_n is an integer, I_n \ge 1 and converges to 0, which is a contradiction. In the second proof, for any natural integer n, we have e =\sum_{k=0}^n\frac {1}{k!}+\int_0^1\frac{(1-t)^n}{n!}e^t dt and for any n, 0 < \int_0^1\frac{(1-t)^n}{n!}e^t dt <\frac {3}{(n+1)!}. .To conclude, in both cases we made assumptions of the opposite as we had a strategy of finding a contradiction during the analysis of the function (another presentation of the same value) that takes advantage of the element in question, namely either \pi or e. Having that in mind, before diving into the very line of contradiction, we should think as how to embed the element in question into the environment in which we feel more comfortable, i.e. in one where we could foresee potential contradictions. To find the contradiction, we just analyze different aspects of the function in the given environment.

Prove that ab+cd is not a prime as an example of looking at the same thing from different perspectives

Let a, b, c, d be integers with a>b>c>d>0. Suppose that ac+bd =k(b+d+a-c) k \in Z. Prove that ab+cd is not prime. Before going further with the proof, I will address a couple of issues.

Firstly, we don’t know what’s the most crucial elements of a certain task. Even if such does not exist, the more we know about the problem, the more likely it is that a reasonably interesting solution or new theory will be created. New perspective enable different decomposition of the problem and a new decomposition allows new attack strategies. To increase the amount of information we know about a specific problem we are going to use computers for gathering information and deduction. In the long run the computers will also be used even more for deduction, thus the need to redefine the position of humans shows up in the horizon.

Secondly, in our task, we do have a certain equation we got used to, thus the very first idea for many is to re-arrange it. That, combined with the fact that the equation contains additional parameter, results in a vision that we are going to be dealing with a proof with multiple cases. Still, such proofs are rarely elegant as instead of the logical chain those represent a set of “if” clauses handled with smaller chains. For the automated theorem proving such an approach would have the potential to give good results due to computational capabilities of computers whilst won’t due to the fact that heuristics is often enough for computers to assume associations without the need for a legitimate rigorous proof.

Those rigorous proofs are still required for the sake of development of strategies thinking whilst it is often the case that computers might take advantage of assumptions, which in certain cases turn into reductio ad absurdium. For problems in the area of automated theorem proving or computational complexity automation of conjecturing the assumptions cuts the domain of definition effectively enough to enable further heuristics. Given a certain degree of pure iteration we face the very useful assumptions and a decision tree with certain branches handled with proofs by contradiction (those branches are pruned later on).

Lets now get back to our initial question. Firstly, in our task there are many trivial cases, those will be omitted in the analysis. We notice that the number we will be checking for primarility is a sum. We don’t have any tools for verification of sums for primarility. I have made a proposition of research in the field of number spectral analysis and the R-sequence, but here omitted. So, for now, we don’t have any method for verification of primility of a sum of two numbers. Now, another set of words from the given task: “not prime”. To show that an integer is not prime, we need to show that it has more than one divisor, i.e. its number of divisors belongs to a set \{2,3,4,5,…$\}$. Lets now assume the number in question is prime. We then have ab+cd=(a+d)c+(b-a)a=m(a+d,b-c) m\in N. For m=1, we have that ab+cd=(a+d,b-c) < a+d, which contradicts with the assumption. For a case (a+d,b-c)=1, we have b+d+a-c|ac+bd, i.e. there exists p such that ac+bd=p(b+d+a-c). Also, ac+bd=(a+d)b-(b-c)a=p(b+d+a-c)=p(a+d)-(b-c)p, thus (p-b)(a+d)=(a+p)(b-c). From the assumption for this case, (a+d,b-c)=1, we have a+p=(a+d)k \rightarrow b-p=k(b-c) \rightarrow a+b=k(a+b+d-c). We also see that if k=1 then c=d, which is a contradiction again. And, for k\ge 2 we have that a+b\ge 2(a+b+d-c) \rightarrow 2c\ge a+b+2d , which again is a contradiction. Given that we fulfilled all the cases, we are done.

From a perspective of automated theorem proving, we would have many special cases and verification of contradictions. So, a computer could do our thing here and this was the reason why I chose this task here. Another thing is to try to understand what what equation might mean. Geometrically, if we have the sum of two fields (a carrot per one lattice point) the same as the field from the RHS, ie. the multiplication, we already see that the LHSes field could be shown as 2d field in integers. And knowing that this equation is true, we have to prove that yet another sum of two fields can also be shown in 2d (it is enough not being prime means that it has at least 2 divisors, i.e. having two divisors is already enough).

And now, knowing the result from the proof with many special cases, we already know the answer, thus based on that might try to judge notice geometrical connections. These could be used for looking at such proofs from yet another perspective, for instance, seeing p_1p_2 as a field of a rectangle. Like in the example of a rectange with a and b is arbitrarily cut into n squares with sides x_{1},...,x_{n}, where we need to show that \frac{x_{i}}{a}\in Q and \frac{x_{i}}{b}\in Q for all i\in\{1,..., n\}. At first sight we see that it is interesting result connecting geometry and numbers. The generally known solution to this task is to express the intersections in the square tilting as a grid and then use a basis of the set of lengths of the squares as representation for constructing two lemmas regarding the grid structure to finally be able to deduce the answer to the question while counting as area of the rectangle by adding all the squares from the grid.

The point

Now, if we take a closer look at both issues, we notice that for building long-way implications regarding and- at the same time- keeping the argument quite self-contained, it might be an effective approach to introduce more varaibles that describe somehow differently the known definition and then look for potential contradictions. In the case of cos1, it was relatively easier than in the case of either \pi or e. Still, in the general case we would have a situation quite similar to the case of the latter, also in many variables. Combining that with visual representation that would be described by the newly introduced variables would give us a chance to deal with the problem twofold, i.e. by visually “noticing” contradictions  (using a finite computational resource, either our head or a computer) or through finding the contradictions as indicated in the first examples and many known results. That combined with a more computational approach to set theorz would  let us use finiatary formulations of infinitiary statements and quite a different approach to mathematical objects (one is more finitary than the other, oracles) and that could be used for automated problem solving using the problem decomposition (from the examples), contradiction search as well as convex optimization for minimizing time of the task being solved.

So, for yet another problem, we would introduce a model based new variables that would describe the known facts and in the same time might allow contradiction search. Such a multi-variable approach would also allow more effective problem handling using a computer. Then, we would have different problem solving strategies ready based on different problem decomposition. The strategies would bid based on the decomposition of the problem as not all might have enough resources to work simulataneously and would bid truthful values to ensure dominant strategy of k-th price auction, taking into consideration resources required. Then, we’d let the winner work first trying to look for contradictions based on the pre-programmed knowledge. The ideas to do that would be used we can derive from these examples, ie. to deduce the most trivial knowledge about the character of two sides of equalities of a specific problem.

Also, regarding the relative construction of geometrical objects so that would could decompose such problems too or decompose other problems into such problems so that our human brain would also be more likely to assist in finding vulnerable points. It would be crucial to note that as of now human brains are better at finding patterns than the computes due to the fact that the knowledge based on numerous senses is, by default, way more strucutred and the patterns are likely more blurred, ie. the comparision of two extensive branches of a tree are less accurate but give useful hints and approximations. Such approximations could be used to build the problem solving strategy before launching the contradiction search process due to the parameter space.

Advertisements

About misha

Imagine a story that one can't believe. Hi. Life changes here. Small things only.
This entry was posted in Mathematics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s