Why is a straight line the shortest distance between two points? The first application I was shown of the calculus of variations was proving that the shortest distance between two points is a straight line. Define a functional measuring the length of a curve between two points:
$$
I(y) = \int_{x_1}^{x_2} \sqrt{1 + (y')^2}\, dx,
$$
apply the Euler-Langrange equation, and Bob's your uncle.

So far so good, but then I started thinking: That functional was derived by splitting the curve into (infinitesimal) - wait for it - straight lines, and summing them up their lengths, and each length was defined as being the Euclidean distance between its endpoints*.

As such, it seems to me that the proof, while correct, is rather meaningless. It's an obvious consequence of the facts that (a) the Euclidean norm satisfies the triangle inequality and (b) the length of a curve was defined as a sum of Euclidean norms.

Getting slightly philosophical, I would conjecture that proving that the shortest distance between two points is a straight line is looking at things the wrong way round. Perhaps a better way would be to say that Euclidean geometry was designed to conform to our sensory experience of the physical world: the length of string joining two points is minimized by stretching the string, and at that point, it happens to look/feel straight.

I'm just wondering whether people would agree with this, and hoping that I may get some additional or deeper insights. Perhaps an interesting question to ask to try to go deeper would be: why does a stretched string look and feel straight?

*: To illustrate my point further, imagine we had chosen to define the length of a line as the Manhattan distance between its endpoints. We could integrate again, and this time it would turn out that the length of any curve between two points is the Manhattan distance between those points.

I think a more fundamental way to approach the problem is by discussing geodesic curves on the surface you call home. Remember that the geodesic equation, while equivalent to the Euler-Lagrange equation, can be derived simply by considering differentials, not extremes of integrals. The geodesic equation emerges exactly by finding the acceleration, and hence force by Newton's laws, in generalized coordinates.

See the Schaum's guide Lagrangian Dynamics by Dare A. Wells Ch. 3, or Vector and Tensor Analysis by Borisenko and Tarapov problem 10 on P. 181

So, by setting the force equal to zero, one finds that the path is the solution to the geodesic equation. So, if we define a straight line to be the one that a particle takes when no forces are on it, or better yet that an object with no forces on it takes the quickest, and hence shortest route between two points, then walla, the shortest distance between two points is the geodesic; in Euclidean space, a straight line as we know it.

In fact, on P. 51 Borisenko and Tarapov show that if the force is everywhere tangent to the curve of travel, then the particle will travel in a straight line as well. Again, even if there is a force on it, as long as the force does not have a component perpendicular to the path, a particle will travel in a straight line between two points.

Also, as far as intuition goes, this is also the path of least work.

So, if you agree with the definition of a derivative in a given metric, then you can find the geodesic curves between points. If you define derivatives differently, and hence coordinate transformations differently, then it's a whole other story.

There are several issues here:

A typo in your equation. Your $y'$ should be squared. That is $y'^2$.
(corrected).
Nothing stops you or me to use other norms. The norm 1 could have issues, since we need the functions $y$, and the "Lagrangian" to be twice continuously differentiable before deriving the Euler-Lagrange equations.
Let us assume you use an $L_4$ norm. Then define the length of a
    path as $\lim_{ | \Delta t | \to 0} \sum  \| \Delta \bf{x}_i \|_4$
    where by $\lim | \Delta t |$ I mean the size of a partition from in
    a real interval $[a,b]$ where the parametric function $\bf{x}(\it
        t)=(x(t),y(t))$ is defined. Then using the same idea of
    differentials you can say $ds = (dx^4 + dy^4)^{1/4}$ and end up with
    another equation $I(y)=\int_A^B (1 + y'^4)^{1/4} dx$. This is
    perfectly fine. You could minimize this cost function, but if you
    apply the Euler-Lagrange equation here you would get:
     \begin{equation}      \frac{d}{dx} \frac{y'^3}{(1+y'^4)^{1/4}}=0 \end{equation}
       and then $y'^3/(1+y'^4)^{1/4}=\text{constant}\equiv C$. The
        solution in    this case is not a straight line.   So what is the
        point?
         It is an optimization problem and the solution and interpretation changes according to the type of norm and space that
you consider. If a distance in kilometers is computed in meters we
need to  multiply by 1000 to compensate for the fact that the new metric
is now
        1/1000 of the old metric. A straight segment in a plane would be deformed (bent or stretched)
        when changing from Euclidean metric to metric such as $L_4$, to adjust to the new shortest path condition. There are two different things that change the solution of the
    problem. The curvature of the space (manifold) being used, and the
    metric that you want to impose. From differential geometry the
    metric tensor $g_{ij}$ is the natural (Riemannian) metric to impose to a curved
    space and this metric generates the geodesics of the system. That
    is, the paths of least distances on that metric. Again, you are free
    to choose another metric, but then those paths will be deformed
    accordingly.
Now, here is a question that I do not see many people (books, documents) asking. It is obvious that we are finding a minimum but this should be proven. That is, is the cost (objective) function convex?
In other words, the solution that the shortest path between two points is straight in $L_2$ norm here in a plane is a necessary but not sufficient condition for stationarity. We still need to prove the "sufficient" part and then ask if the minimum is a local or global  minimum, if it is unique. Seems obvious but how to prove this?
Here is an interesting argument which does not require smooth constraints and the sofisticated Euler-Lagrange machinery.
We search for the shortest path length $L(A,B)$ between two points $A$ and $B$. The distance is an invariant under translation and rotations (those are isometries). Then without loss in generality we can think that $A=(0,0)$ the origin and $B=(0,\ell)$, where $\ell$ is the straight distance between $A$ and $B$. Then the length of any segment between $A$ and $B$ is given by
\begin{equation}
L(A,B) = \int_0^{\ell} \sqrt{1+ y'^2} dx \ge \int_0^{\ell} dx = \ell.
\end{equation}
since $y'^2 \ge 0 $. So $\ell$ is a lower bound for lengths over all
qualifying segments. Even more, the straight distance is $\ell$, so
$\ell$ is the infimum, the minimum, and the shortest distance.
If you pick a metric inherited from $L_4$ norm, you would get also,
doing the same analysis that $\ell$ is a lower bound of all qualifying
paths between $A$ and $B$, but this time $\ell$ is smaller than the
possible shortest measure under this new metric.
So, metrics induced by the norm
$L_n$, $n > 2$, create longer shortest paths (at least for $n$ even,
what happens if $n$ is odd?). This makes sense in the
case of the sphere, where a straight segment is shorter than a geodesic on the sphere.

It is obvious that there is not upper bound for the distance. You give me a distance and I can always find a path which is longer. The question is: does the distance has a lower bound? The answer is "yes" since distance is always greater or equal to zero, so it has an "inf".  Still, if the infimum is unique this does not mean that the path is unique. Think of a distance on a unit sphere between two antipodes. There are an infinite number of paths which satisfy the shortest path of length $\pi$. In the case of a path on a plane we can use Euclid's postulate: There is only one line through two points. So it is unique. It rest to prove: Is the infimum the length of the line between those two points?

For an excellent discussion on the topic of this question please check:
A course in Metric Geometry  chapter 2.


Is $y=\frac{x^{2}-1}{x-1}\;,\;x\neq1$ belong to two-variables linear equation? I have an equation as below:

$$y=\frac{x^{2}-1}{x-1}\;\;,\;\;x\neq1$$

Question:
Does it belong to two-variables linear equation?

My effort:
The equation can be simplified
$$y=\frac{(x+1)(x-1)}{(x-1)}\;\;,\;\;x\neq1$$
$$y=x+1\;\;,\;\;x\neq1$$
The equation above in the form y = mx + c but I think it is not belong to two-variables linear equation because there is a hole (1,2) in line graph. Is it true?

If you calulate $\lim\limits_{x\rightarrow1}f(x) = 2$
This limit is FINITE!
You can thus create an alternate function $\tilde f$ defined by
$$\tilde f(x)=\left\{
\begin{matrix}
\frac{x^2-1}{x-1}\ \text{ if }\ x\ne1\\
2  \text{ if }\ x=1
\end{matrix}
\right.$$
Which is a continuous function and is equal to $y=x+1$ everywhere


Is there any good reason not to define $0^0=1$ , such as contradictions in algebra or arithmetic? Math people:

The title is the question: Is there any good reason not to define $0^0=1$ , such as contradictions in algebra or arithmetic?

I searched for similar questions before I posted this question, and couldn't find any.  After I posted it,  I got some comments citing similar questions.  There is a similar question at What values of $0^0$ would be consistent with the Laws of Exponents? .  I checked some of the other questions in the links in the comments and the links posted with those links.  There is a closer match at How to define the $0^0$? That question was closed as a duplicate, but the older, duplicated question was not identified.  I could not find a convincing answer anywhere to my essential question: "does defining $0^0=1$ lead to contradictions in algebra and arithmetic?" I'll leave it up to others to decide whether my question is a duplicate.  If it is, maybe you can close this question and give a better (in my opinion) answer to one of the older questions.

Let me get one thing out of the way up front: yes, I know "$0^0$" is an indeterminate form.  That is, if $f$ and $g$ are real-valued functions with $f(t) \to 0^+$ as $t \to 0$ and $g(t)\to 0$ as $t \to 0$, then you don't know what $\lim_{t\to 0}f(t)^{g(t)}$ is, or even whether exists, without more information.  I don't consider this a good reason to declare that $0^0$ itself must be considered undefined.  I know many people will disagree with me here.  I expect at least one answer and some comments arguing why this is a good reason for $0^0$ to be considered undefined.  Everyone is entitled to their opinion, and you are free to leave such an answer.  I will not attempt to change your mind, beyond what I write in this question.

If you define $f(x,y) = x^y$, then $f$ cannot be continuous on $[0,\infty) \times \mathbb{R}$ no matter what value, including $1$, you assign to $f(0,0)$.  But why should every function have to be continuous?

If the mathematical community ever does come to the consensus that $0^0=1$, and I were teaching calculus students about limits involving indeterminate forms, I probably would not even mention the question of whether $0^0$ itself had a value, because it probably just confuse the students.  They probably wouldn't even notice the omission.

To me, a "good reason" not to define $0^0=1$ would be if this definition resulted in a contradiction, when used in expressions involving multiplication and exponentiation of real numbers and the rules used to simplify such expressions.  Here is an attempt to produce such a contradiction: assuming $0^0=1$, $(0^0)^2=1^2=1$, and $(0^0)^2=0^{(0*2)}=0^0=1$.  No contradiction.  In constrast, if you define $0/0 = 1$ and you want the associative property to hold (a reasonable expectation), then you can derive the contradiction $1=0/0=(2*0)/0=2*(0/0)=2*1=2$.

It just occurred to me that there is another good reason for not declaring officially that $0^0$ must always equal $1$: if defining $0^0=0$ does not lead to contradictions in algebra or arithmetic, either.

I am not claiming $0^0 = 0/0$.  Of course you can never divide by zero, or raise zero to a negative power.

Of course, when people use power series, they use $0^0=1$ all the time, and no one complains.  I have read that "$0^0=1$" is used often in combinatorics, but I don't know much about combinatorics.

Based on what I have seen in the older questions, their answers, and the answers and comments to this question, it seems that no one has discovered any way in which defining $0^0$ to be $1$ leads to contradictions when using the usual rules of multiplication and exponentiation.  It also seems that defining $0^0$ to be $0$ does not lead to such a contradiction. So I'm guessing it is impossible to produce such a contradiction.  But I have never heard of anyone wanting to define $0^0$ as $0$.

At the very least, the answer $0^0 = 1$ is consistent with cardinal arithmetic on the set $\{0, 1, 2, \ldots\}$. Under this interpretation, the number $m^n$ is defined to be the number of functions from an $n$-element set to an $m$-element set. There is exactly one function from a $0$-element set to a $0$-element set, so in this interpretation, $0^0 = 1$. The laws $a^m a^n = a^{m+n}$ and $(a^m)^n = a^{mn}$ can be proven with that definition. Thus, exponentiation as repeated multiplication can be recovered. (In one of your links, Matt N. gives this same idea as an answer.)

The first criticism I heard involved the subtraction law $\frac{a^x}{a^y} = a^{x-y}$. The idea is that $\frac{0^x}{0^x} = 0^0$, yet $\frac{0^x}{0^x} = \frac{0}{0}$, so $0^0$ is undefined. The problem here isn't with $0^0$, it's with saying $\frac{0^x}{0^x}$ is equal to anything, when it is undefined. We could use the same reasoning to say that $0^2$ is undefined, since $0^2 = \frac{0^7}{0^5} = \frac{0}{0}$. At worst, the subtraction law has to be modified to say that it only applies when $a^y \neq 0$. We make such modifications for all of our other laws involving division, so why should this be any different?

The fact that 0^0 = 1 follows directly from a widely accepted theorem (the
binomial theorem). Thus, the claim that 0^0 is undefined is equivalent to the claim that widely accepted mathematical results are mutually inconsistent.

This is a huge claim considering the fact that nobody has found any inconsistencies in over a hundred years!

The reality is that (a) 0^0 is 1 in every formula that contains x^n,
(examples: binomial theorem, Taylor series, polynomials, Vandermonde matrix, power rule, etc.), and (b) nobody has ever found any contradiction arising from this.

In all other parts of mathematics if A ==> B, and A is a widely accepted theorem, then we must accept B as well. Nevertheless, some people reject this when B is a statement that conflicts with their gut intuition such as 0^0 = 1. They would rather rely on ad-hoc arguments like limits instead of accepting corollaries of well established theorems.  The only explanation I can come up with for this phenonemon is that even in the modern age, people are still uncomfortable with accepting 0 as a number, or {} as a set.


What is the meaning of an "objective function" and "objective functionals"? Right now I am in front of these expressions

objective function

objective functionals

which seem to be very often used, but I've still not understood their meanings.

The concept of $objective$ $function$ is used in optimization. It denotes the function you want to minimize or maximize. It is used in many areas as in curve fit, regression, economics, ...

If there is any relevant area you would like to discuss, just post.

Just by the way, I was born in Dar El Beida (normal name hidden !).

In general terms or simple english:

Objective: What is the goal?

Function: How to measure performance?

For mathematical details:

http://en.wikipedia.org/wiki/Objective_function

http://en.wikipedia.org/wiki/Optimization_problem


Questions about $d(x,A)$ and $\operatorname{diam}(A)$ in a metric space I have 2 questions, one each for $d(x,A)$ and $\operatorname{diam}(A)$, where $A$ is a nonempty subset of a metric space $(X,d)$. Both of them are somewhat related to each other. The first one is about the following statement.

  There exists $y\in\bar{A}$ such that $d(x,A)=d(x,y)$.

I figured that this is the case when $X=\mathbb{R}^n$, but my proof relies heavily on the Bolzano-Weierstrass theorem (every bounded sequence has a convergent subsequence) and I can't figure out how I should generalize this to general metric spaces. If this is not true for general metric spaces, how further can we generalize?

The second one is about $\operatorname{diam}(A)$:

  If $\operatorname{diam}(A)<\infty$, then there exist $x,y\in\bar{A}$ such that $\operatorname{diam}(A)=d(x,y)$.

Again, my proof relies heavily on the B-W theorem (and the fact that the function $d:X\times X\rightarrow\mathbb{R}$ is continous) and I can't figure out a way to avoid B-W in the argument. Is this not true in general? If so, can someone provide me illustrative counterexamples?

For counterexamples for the general case, consider $A=\{(x_1,x_2)\in\mathbb{Q}^2\,|\,x_1^2+x_2^2=1\}$ and $x=(1,1)$ in $X=\mathbb{Q}^2$ for the first case and $A=(-\sqrt{2},\sqrt{2})\cap\mathbb{Q}$ and $x=2$ in $X=\mathbb{Q}$ for the second case. This means that completeness is something to be assumed.

For counterexamples in the complete case, consider the complete metric space $\ell^2(\mathbb{N})$ whose elements are all infinite sequences $(x_n)$ of real numbers such that $\sum_n\,x_n^2<\infty$ and whose metric is given by
$$d((x_n),(y_n))=\sqrt{\sum_{n=1}^\infty\,(x_n-y_n)^2}\text{.}$$
It is a classic result and/or an interesting exercise that this is effectively a complete metric space. In this space:

Taking $A=\{(1+1/n)e_n\,|\,n\geq 0\}$, where $e_n$ is the sequence with a $1$ in the $n$-th position and $0$ in the rest, and $x=0$, we have that $A$ is closed, $d(x,A)=1$ and $d(x,y)>1$ for all $y\in A$. Thus this is a counterexample for the first statement.
Taking $A=\{(1-1/n)e_n\,|\,n\geq 1\}$, we have that $A$ is closed, $\mathrm{diam}(A)=2$ and $d(x,y)<2$ for all $x,y\in A$. Therefore this is a counterexample for the second statement.

In conclusion, even in the complete case there are counterexamples for your two statements. This means (up to what I can think) that a compactness assumption (e.g., that every closed ball is compact) is essential, as it has happened to you in the case of $\mathbb{R}^n$.

The answer of both of questions is related a theorem which states " Every continuous function defined on a closed(compact) set attains its supremum   and infimum "
By definition we have $d(x,A)=inf\{d(x,a)|a\in A\}$ note that this function attains its  infimum then there exists $a\in A$ such that $d(x,A)=d(x,a).$


Do these two definitions of "open set" consist? I am new to topology and have just encountered a definition of open sets:

Let $T$ be a topology on a set $X$, any element in $T$ is called an open subset.

But in the earlier analysis course, the definition of open set is:

For E as a subset of a metric space $X,d$, E is open if for all $x$ belongs to $E$, exists $\epsilon>0$ such that $B_\epsilon(x)$ is a subset of $E$.

I cannot see the connection between these two definitions so far.
As both of them define the concept of open sets, I think they should be equivalent or at least consistent. So could someone tell me to see if they consists?

Thanks so much!

One way in which math advances is that we create new generalizations that allow us to apply old ideas into new contexts.

This process requires us to create a new definition that extracts some key properties of the old definition in the old context, show how that definition can match the old definition in the old context, prove results from those properties, and then apply them to new contexts.

As you learned in analysis, the idea of open sets comes from metric spaces.  And notions such as "continuity" come from what the open sets on the metric space are.  You can change the metric a lot, but as long as the open sets remain the same, a lot remains the same.

So our generalization is to declare the set of open sets to be something called a topology.  We then write down a set of axioms that the set of open sets in a metric space satisfy.  And we call the set of open sets in a metric space to be the topology induced by that metric.  In the case of metric spaces, "open set" still means the same thing that it used to, and all of the old results apply.  But now we can apply the idea in new contexts, and get new results of interest.

They are consistent in a metric space where the topology is generated by the distance function.

Given some set $X$ and $T$ a family of subsets of $X$, we'll say $(X,T)$ is a topological space if it satisfices:

$\emptyset,X\in T$

$\forall U,V\in T,U\cap V\in T$

$\forall \lbrace U_i\rbrace_{i\in I}\subset T,\bigcup_{i\in I}U_i\in T$

Also we define, given some family $B$ that satisfices $\forall U,V\in B,\forall x\in U\cap V,\exists W\in B:x\in W\subset (U\cap V)$ and $\bigcup_{U\in B}U=X$, the topology spanned by $B$ as $T=\lbrace \bigcup_{i\in I}U_i:\lbrace U_i\rbrace_{i\in I}\subset B\rbrace$. We say $B$ is a base of $T$.

Given these definitions, we can prove that $\mathcal{B}=\lbrace B(x,r):x\in X,r\geq0\rbrace$ is the base of the family of open sets, as you defined in your previous course of analysis, wich is a topology (since satisfices the three properties above). In other words the topology spanned by $\mathcal{B}$ coincides with the family of open sets in a metric space.


Can cos(n!) in degrees tend to one if n>6? does cos(n!)  in degrees tend to 1.
consider cos(n!)=cos(n*...*6!),6!=720=360*2.So this is like rotating on the plane n*...7*2 times so cos(n!)=1,When n>6 .Does this proof hold even when n tends to infinity.please give a reply which suits the mind of a beginner.

Indeed $\cos (n!) = 1$ for $n \geq 6$ since $n! \equiv 0 \pmod{360}$. But $n$ must be a finite number, $\cos \infty$ makes no sense, but we can say that $\displaystyle\lim_{n\to\infty} \cos (n!) = 1$:

We say that the sequence $\{a_n\}$ tends to the finite limit $l$ as $n$ goes to infinity if:

$\forall \varepsilon >0\ \exists n_0 > 0$ so that if $n > n_0$ then $|a_n - l| < \varepsilon$.

Taking $l = 1$ and $n_0 = 5$ then regardless of how $\varepsilon$ is, the definition holds, so indeed, $$\lim_{n\to\infty} \cos (n!) = 1$$

Using Riemann zeta function,infinite factorial can be regularized $$\prod_{n=1}^\infty\lambda_n=\exp(-\zeta'_{\lambda}(0))\\\zeta_\lambda(s)=\sum_{n=1}^\infty \lambda_n^{-s}\\\zeta_\lambda'(s)=-\sum_{n=1}^\infty\lambda_n^{-s}\log(\lambda_n)$$
Plugging in $\lambda_n=n$ we get that
$$\prod_{n=1}^\infty n=\infty!=\sqrt{2\pi}$$
NOTE: $\zeta'(0)=-\frac{1}{2}\ln({2\pi})$ which can be derived directly from the Wallis formula

So $\cos(\infty!)=\cos(\sqrt{2\pi})\approx0.99904$


Prove the following statement by combinatorial argument. Prove the following statement by combinatorial argument:-
$({n \choose0}+{n \choose1})×({n \choose1}+{n \choose2})×\cdots×({n \choose n-1}+{n \choose n})= \frac{{n \choose0}{n \choose1}{n \choose2}\cdots{n \choose n}}{n!}×(1+n)^{n} $

Well I found this question from my friend, a math lover and me too.. i thought that I could do the sum but it was confusing my mind.  I am weak in making combinatorial argument so I need a help to withstand the problem so I posted here.

Hint:

You can use  $${n\choose k-1}+{n\choose k} = {n+1\choose k}$$

and a fact that $${n+1\choose k}= {(n+1)!\over k!(n+1-k)!} $$ $$={n+1\over n+1-k }\cdot  {n!\over k!(n-k)!} = {n+1\over n+1-k } {n\choose k}$$


Question about the definition of a category I am confused about the definition of a category given in the Wikipedia article on Category theory:

It seems to me that the structure being described (the "arrows" between objects in some class) is just a binary relation that is both reflexive and transitive. If so, what is meant by the set of all morphisms (arrows) from one object to another? The definition says that every morphism (arrow) has a unique source object and target object. Is there not then at most one arrow from one object to another?

EDIT 1

I am looking for formal axioms of category theory expressed only in the notation of first-order logic and set theory -- no words, just variables, functions, logical connectors, quantifiers, predicates, '=' signs, '$\in$', etc.

EDIT 2

How about: class $ob$ is a category iff...

$\forall a,b \in ob\exists hom \forall f(f\in hom \leftrightarrow \forall d\in a(f(d)\in b)) $
$\forall a\in ob\exists i \forall b\in a(i(b)=b)$

Note that the required properties of composition are a direct result of functionality of each morphism.

EDIT 3

I must be trying the patience of the moderators here. Sorry guys! This has turned into a rather open-ended discussion. To be continued at the sci.logic and sci.math newsgroups:

https://groups.google.com/group/sci.logic/browse_frm/thread/bd8d78c920e1d28c#

EDIT 4

I'm not sure this is right either, but you might consider the following.

I define the Category and Arrow predicates as follows:

$\forall x (Category(x) \leftrightarrow \forall y\in x \exists f \forall z\in y (f(z)=z))$

This would be redundant if the elements of x were all sets because you can prove the existence of an identity function on every set.

$\forall x\forall a,b\in x (Arrow(x,a,b) \leftrightarrow a\in x
\land b\in x \land \exists f \forall c\in a (f(c)\in b) \land \forall c\in b \rightarrow \exists d\in a (f(d)=c)$

It is then easy to prove that the Arrow relation is reflexive:

$\forall x (Category(x) \rightarrow \forall a\in x Arrow(x,a,a))$

And that the Arrow relation is transitive:

$\forall x (Category(x)\rightarrow \forall a,b,c\in x (Arrow(x,a,b) \land Arrow(x,b,c) \rightarrow Arrow(x,a,c)))$

Thanks all for your help.

You're misinterpreting the meaning of the word "unique" (which was poor word choice on the part of whoever wrote that, so I am removing it). It just means that an arrow doesn't have more than one source or target.

Here is a formal definition of a small category (this will allow me to ignore size issues which I think are irrelevant when first trying to understand category theory). I'm afraid I'm too attached to words to follow the "no words" edict, but I hope this will be formal enough. A category consists of the following data:

A set $\text{Ob}$ (objects),
For every $a, b \in \text{Ob}$, a set $\text{Hom}(a, b)$ (morphisms from $a$ to $b$),
For every $a \in \text{Ob}$, an element $\text{id}_a \in \text{Hom}(a, a)$ (identity),
For every $a, b, c \in \text{Ob}$, a function $\circ : \text{Hom}(a, b) \times \text{Hom}(b, c) \to \text{Hom}(a, c)$ (composition).

(I am writing function composition in the opposite of the usual order. You should think of a morphism $f \in \text{Hom}(a, b)$ as an arrow $f : a \to b$ pointing from $a$ on the left to $b$ on the right.)

This data is subject to the following axioms:

Identity: for every $f \in \text{Hom}(a, b)$, we have $\text{id}_a \circ f = f$, and for every $g \in \text{Hom}(b, a)$, we have $g \circ \text{id}_a = g$.
Associativity: for every $f \in \text{Hom}(a, b), g \in \text{Hom}(b, c), h \in \text{Hom}(c, d)$, we have $f \circ (g \circ h) = (f \circ g) \circ h$.

Some concrete classes of examples to keep in mind ("categories-as-mathematical-objects" rather than "categories-as-settings-to-study-mathematical-objects") are the following:

A monoid is a category with one object; that is, $\text{Ob}$ is a one-element set. The elements of the monoid are the morphisms from the unique object to itself.
A poset is a category in which $\text{Hom}(a, b)$ has either $1$ or $0$ elements (corresponding to whether $a \le b$ or not); moreover, if $\text{Hom}(a, b)$ and $\text{Hom}(b, a)$ both have one element, then $a = b$. The existence of identities expresses reflexivity, the composition law expresses transitivity, and associativity is automatic.
A groupoid is a category in which every morphism $f : a \to b$ has an inverse $g : b \to a$, which is a morphism satisfying $f \circ g = \text{id}_a, g \circ f = \text{id}_b$. Groupoids are a simultaneous generalization of groups, equivalence relations, and group actions. An important example is the fundamental groupoid $\Pi_1(X)$ of a topological space $X$, which is the groupoid whose objects are the points of $X$ and whose morphisms are the homotopy classes of paths between points in $X$; composition is given by concatenating paths.

One example of "categories-as-settings-to-study-mathematical-objects":

The "matrix category" $\text{Mat}$ is the category whose objects are the non-negative natural numbers $\mathbb{Z}_{\ge 0}$ and whose morphisms $\text{Hom}(n, m)$ are the $n \times m$ matrices, say over some ring (or $m \times n$; whichever convention makes composition correspond to matrix multiplication).

Concrete Categories

Let $ob$ be a class such that

$\forall a (a\in ob \leftrightarrow P(a))$

for some property $P$.

Then $ob$ is a concrete category iff...

(1) $\forall a,b \in ob(\exists hom (\forall f(f\in hom \leftrightarrow (\forall d\in a(f(d)\in b) \land \exists d\in ob \forall e\in d\exists g\in a (f(g)=e)))))$

where the $f$'s are morphisms (functions) that map set $a$ to set $b$ preserving property P, and $hom$ is the set of all such morphisms.

(2) $\forall a\in ob(\exists i \forall b\in a(i(b)=b))$

where the $i$'s correspond to identity morphisms.


How do I find the probability of some elements being together inside a randomly arranged set? If I have a total of $n$ balls made of $k$ red balls and $(n-k)$ green balls and I arrange them all randomly in a line, how can I calculate the probability $x$ of a group of $y$ red balls being together?

If $k=y$, the solution would be $x=\frac{k!}{n!}$, but I'm striving to find how to deal with cases where $k>y$.

Not an answer in closed form, but it might be useful. I am preassuming that your conditions are also met if there are more than $y$ red balls together.

Let $E_{n,k}$ denote the event that by arranging $k$ red balls and
$n-k$ green balls there will be a consecutive row of at least $y$
red balls.

Let $R+1$ denote the spot of the first green ball.

Evidently
$r\geq y$ implies that $P\left(E_{n,k}\mid R=r\right)=1$ and $r<y$
implies $P\left(E_{n,k}\mid R=r\right)=P\left(E_{n-r-1,k-r}\right)$.

Next to that we have $P\left(R=r\right)=\frac{k}{n}\frac{k-1}{n-1}\cdots\frac{k-r+1}{n-r+1}\frac{n-k}{n-r}$
for $r=0,1,\dots,k$.

There is a recursive relation: $$P\left(E_{n,k}\right)=P\left(R\geq y\right)+\sum_{r=0}^{y-1}P\left(E_{n-r-1,k-r}\right)P\left(R=r\right)$$

Btw, there is some resemblance with this question that deals with "with replacement".

Note: Going by what I believe is the intent of the question, I have made 2 assumptions:

(a) There are at least 2 green balls

(b) k < 2y

Withdraw y red balls and cushion them on each end with a green ball.

Balls remaining in the original group are (k-y) red and (n-k-2) green       totalling (n-y-2) with the red placed in the group in **${n-y-2}\choose{k-y}$ ways.

You have a sequence G - y reds - G treated as a block to be placed among the     gaps between the (n-y-2)  balls including ends i.e. in (n-y-1) available spots.
Pr = (n-y-1)*${n-y-2}\choose{k-y}$/${n}\choose{k}$


Did I pick the error? Mathematical Logic Given these propositions:
$$\begin{align}
x&=y \\
x^2&=xy \\
x^2-y^2&=xy-y^2\\
x+y&=y\\
y+y&=y\\
2y&=y\\
2&=1
\end{align}
$$
I've found out that the error is "$x+y=y$". Am I correct? I'm just a beginner in Discrete Math.

Um, sort of? It's supposed to be factoring both sides of the equation into

$$(x-y)(x+y)=(x-y)y$$

and dividing by $x-y$ to yield

$$x+y=y$$

which seems fine at first glance. But the problem is when you divide by $x-y$ you're actually dividing by $0$ because $x=y$.

The fish rots from the head: $x=y\Leftrightarrow x^2=xy$ holds iff $x\neq0$.


Computing sample variance and error using Monte Carlo Asked to compute estimator for the following function,

$$\theta = \int_0^\infty \mathrm{e}^{-x^2}~\mathrm{d}x$$

which can be solved by transforming the limits to 0 to 1 and solving the following expectation using Monte Carlo,

$$ E\left[\frac{1}{U^2}~\mathrm{e}^{-(-1+1/U)^2}\right]$$

where $U$ is uniformly distributed

The estimator is,
$$\hat\theta = \frac{1}{N} \sum_0^n \frac{1}{U} \space \mathrm{e}^{-(-1+1/U)^2} $$

How do I go about computing the sample variance and then the error? How can I compute the variance without knowing the population mean?

Are there any formulas to choose the best $N$?

You probably mean to use the identity
$$\theta= E\left[U^{-2}\mathrm{e}^{-(-1+1/U)^2}\right],$$
where $U$ is uniformly distributed, and the sequence of estimators $(\hat\Theta_n)_{n\geqslant1}$ defined as
$$\hat\Theta_n = \frac{1}{n} \sum_{k=1}^nV_k,\qquad V_k= U_k^{-2}\mathrm{e}^{-(-1+1/U_k)^2}.
$$
Then,
$$
E(\hat\Theta_n)=E(V_1)=\int_0^1u^{-2}\mathrm e^{-(1-u)^2/u^2}\mathrm du=\int_0^\infty\mathrm e^{-x^2}\mathrm dx=\theta,
$$
by the change of variable $x=(1-u)/u$, $u=1/(x+1)$,
and
$$
\mathrm{var}(\hat\Theta_n)=\frac{\sigma^2}n,\qquad\sigma^2=\mathrm{var}(V_1).
$$
Note that
$$
E(V_1^2)=\int_0^1u^{-4}\mathrm e^{-2(1-u)^2/u^2}\mathrm du=\int_0^\infty(x+1)^2\mathrm e^{-2x^2}\mathrm dx,
$$
by the same change of variable. Thus,
$$
\theta=\frac12\sqrt\pi,\quad E(V_1^2)=\frac12+\frac5{16}\sqrt{2\pi},\quad\sigma^2=\frac12+\frac5{16}\sqrt{2\pi}-\frac14\pi.
$$

  Are there any formulas to choose the best $N$?

Sorry? The larger $n$ is, the more accurate the estimate $\hat\Theta_n$ is.

You can also calculate $(\int_0^\infty e^{-x^2}dx)^2=(\int_0^\infty e^{-x^2}dx)(\int_0^\infty e^{-x^2}dx)=(\int_0^\infty e^{-x^2}dx)(\int_0^\infty e^{-y^2}dy)=(\int_0^\infty\int_0^\infty e^{-x^2}e^{-y^2}dxdy)=\int_0^\infty\int_0^\infty e^{-(x^2+y^2)}dxdy$.

Now we use polar coordinates, and let $x=r\cos(\theta),y=r\sin(\theta)$, $r^2=x^2+y^2$ ($0\leq r\leq\infty$), $\,$ $(0\le\theta \leq2\pi)$. now we have:

$\int_0^\infty\int_0^\infty e^{-(x^2+y^2)}dxdy=\int_0^{2\pi}\int_0^\infty re^{-r^2}drd\theta=(\int_0^{2\pi}1d\theta)(-\frac{1}{2}e^{-r^2}|^\infty_0)=\pi$.

Taking the square root we get $\int_0^\infty e^{-x^2}dx)^2=\sqrt{\pi}$

I hope that may help.


Solve : $x^2-92 y^2=1$ As some of you might know,this is Brahmagupta's equation . How to find solution for this ?
I mean integral solution? How to solve it using programming ?

I tried something like $x^2=1+92y^2$

$x=\sqrt{1+92y^2}$

Use brute force approach to check for every y ? Is there any better answer ?

I think the most common systematic way to solve this type of problem is using continued fractions. I'll reiterate @Quimey's suggestion to refer to Wikipedia for Pell's Equation
and specifically the section "Fundamental solution via continued fractions" and the Lenstra paper cited there.

In this case as a periodic continued fraction
$$
\sqrt{92} = [9;1,1,2,4,2,1,1,18,1,1,2\ldots] = 9+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{4+\cfrac{1}{2+\cdots}}}}}
$$
and after 7 terms we get the approximation $\sqrt{92}\simeq 1151/120$ which gives the fundamental solution.

As for implementing an algorithm for finding the continued fraction for square roots, you should be able to find resources online with a search, but can start by taking a look at this question.

def pr_sol(maxval,N,ee,ff):
    count=0
    aa,bb=0,1
    gg=N*ff
    while count<maxval:
        if bb**2 - 1 ==N*aa**2:
            print(bb,'^2-1=',N,'*',aa,'^2')
        else:
            print(bb,'^2+1=',N,'*',aa,'^2')
        anew=ee*aa+ff*bb
        bnew=gg*aa+ee*bb
        aa=anew
        bb=bnew
        count+=1
  return

pr_sol(20,92,1151,120) #print first 20 solutions when N=92
""" the smallest solution is 1151,120 where
1151 ^2-1= 92 * 120 ^2  (from wikipedia).
(I'm not sure if it's the same as wikipedia recursion,
but in this case the following recursion applies:
a_{t+1}=1151*a_{t} +120*b_{t}
b_{t+1}=120*92*a_{t} +1151*b_{t}
(in general you can generate such a recursion, which gives
values for x^2-1=Ny^2  AND x^2+1=Ny^2
(but x^2 ==91 mod 92 has no solutions so
there are no sol to x^2+1=Ny^2 ))

The first few solutions are:
1 ^2-1= 92 * 0 ^2  (a,b)=( 0 , 1 )
1151 ^2-1= 92 * 120 ^2 (a,b)=( 120 , 1151 )
2649601 ^2-1= 92 * 276240 ^2 (a,b)=( 276240 , 2649601 )
6099380351 ^2-1= 92 * 635904360 ^2
14040770918401 ^2-1= 92 * 1463851560480 ^2
32321848554778751 ^2-1= 92 * 3369785656320600 ^2
I've just been doing some investigation into these equations
and found this recursion. (which has some advantage. For
example N=313 has very large first solution to x^2-1=Ny^2 but
you can generate the numbers from the much smaller solution:
126862368^2 +1 =313 *  7170685^2
and the recursion:
a_{t+1}= 126862368 a_t+7170685 b_t
b_{t+1}=313*7170685a_t+126862368  b_t
so
pr_sol(20,313,126862368,7170685)
prints first 20 solutions for N=313
(note they alternate between x^2+1=313y^2 and x^2-1=313y^2)

"""


Find a function that satisfies the condition. Let $\epsilon > 0$ be fixed and $t$ a variable that takes values in the universal covering space of ${\mathbb{C} \setminus \{0\}}$.

Find a continuous function $f(s$) such that
$$|t \log t| = |t| \sqrt{(\ln |t|)^2 + (\arg t)^2} < \epsilon$$
whenever $|t| < f(\arg t)$.

Note: Basically, since $t$ is in the universal covering space of ${\mathbb{C} \setminus \{0\}}$, $\log {t}$ and $\arg {t}$ are well-defined functions and not multi-valued like they usually are.

New strategy: Replace $\lvert t \rvert$ and $\arg t$ by real variables $r>0$ and $\theta$, respectively. Define $g_\theta \colon \mathbb R_{>0} \to \mathbb R_{>0}$ by $g_{\theta}(r) = r^2((\ln r)^2 + \theta^2)$; note that this last expression is essentially the square of the expression we are interested in. Construct a continuous function $h \colon \mathbb R \to \mathbb R_{>0}$ so that $g_\theta(r) \leq h(\theta) \cdot r$ for all $r \leq 1$ and $\theta \in \mathbb R$.

Edit (2014-06-21): Since the asker has been inactive for almost a month now, I'm just going to write down the full solution and put it in the spoiler block below. Hover your cursor over to unhide the text.

   It suffices to find a continuous function $f \colon \mathbb R \to \mathbb R_{>0}$ such that for $r>0$ and $\theta$ real, we have $$r^2\bigl((\ln r)^2 + \theta^2\bigr) < \epsilon^2$$ whenever $r < f(\theta)$. Note first that since $\lim_{r \to 0} r (\ln r)^2 = 0$, we can use compactness to argue that the function $r \mapsto r(\ln r)^2$ is bounded on $(0,1]$. Pick an upper bound $\alpha$ (one can use calculus to show that $\alpha = 4/e^2$ is the smallest possible choice). If we now define $f$ by $$f(\theta) = \min\left\{1, \frac{\epsilon^2}{\alpha + \theta^2}\right\},$$ then when $r < f(\theta)$, we obtain $$r^2\bigl((\ln r)^2 + \theta^2\bigr) = r\bigl(r(\ln r)^2 + r \theta^2\bigr) < r\bigl(\alpha + \theta^2\bigr) < \epsilon^2$$ as desired.

A good strategy I've learned throughout undergraduate mathematics courses is to always simplify, and reword. It usually helps see a problem from a different perspective. Going off this notion, I'll make a few points

$|t\log{t}| = |t||logt| = |t|\sqrt{ (ln|t|)^2} + (\arg t)^2)$
So essentially the important parts of this equality is that $|logt| = |t|\sqrt{ (ln|t|)}^2 + (\arg t)^2)$
Rewording the problem, your problem is finding f(s) so that

$|t| < f(arg t) \implies |\log(t)| = |t|\sqrt{ (ln|t|)^2} + (\arg t)^2)$

From here, I suggest maybe isolating $\arg t$ so that your new statement is simplified. I think this will provide more insight into solving the problem. Hope this helped, if even a little. And sorry about the poor formatting, still getting used to posting answers. Good luck!


Show that the set in the ring of polynomials in $\mathbb Q[x]$ is an ideal of $\mathbb Q[x]$. In the ring of polynomials with rational coefficients $\mathbb Q[x]$, let

$$I = \{h(x) \in \mathbb Q[x] : (x^2 - 2)  \ \text{  divides  }\ \  h(x)\}$$

Show $I$ is an ideal of $\mathbb Q[x]$.

I know I must show that the set is an additive subgroup and that if $s\in I$ and $r\in R$ then $rs$and $sr \in  I$, but I am getting confused with the divider property in the first steps. Any help with this proof would help.

Also, how would I be able to show if this was a maximal ideal?

Thank you.

The condition that $x^2 - 2$ divides a polynomial $h(x) \in \mathbb{Q}[x]$ means that there exists $g(x) \in \mathbb{Q}[x]$ such that $h(x) = (x^2 - 2)g(x)$, i.e. $x^2 - 2$ is a factor of $h(x)$. Now if you have two polynomials $h_1(x)$ and $h_2(x)$ in $I$, then $(x^2 -2 )$ is a factor of both, a common factor. So we can write $h_1(x) + h_2(x) = (x^2 - 2)f(x)$ for some $f(x)$ and you can see the sum is in $I$. The other conditions you need to check follow similarly.

To see that $I$ is maximal, you just need to show that $x^2 - 2$ is irreducible (see why?). This follows from Eisenstein's criterion.

Edit: To go from irreducible polynomial to maximal ideal, you can proceed as follows: Suppose $J\subseteq \mathbb{Q}[x]$ is an ideal that properly contains $I$, so $I \subsetneq J$, and let $f \in J \setminus I$. Then $x^2 - 2$ doesn't divide $f$ (since $f \not\in I$) so their GCD is 1. By the Euclidean algorithm, you can find polynomials $s$ and $t$ such that $1 = f\cdot s + (x^2 - 2)\cdot t$. From here (check!) you get that $1 \in J$, hence $J = \mathbb{Q}[x]$. Thus the only ideal properly containing $I$ is the whole ring, so $I$ is maximal.


Negative eigenvalues of Sturm-Liouville problem I am trying to solve the following Sturm-Liouville problem on the circle $S^1$, i.e. the closed interval $[0,1]$ with periodic boundary conditions $(y(0)=y(1))$: $$\frac{d}{dx}\left[\frac{1}{p(x)}\frac{dy}{dx}\right]+\frac{1}{p(x)}(p^2(x)+\frac{1}{2})y=-\frac{\lambda}{p(x)}y.$$ Here $p$ is a positive function and is also the first eigenfunction (corresponding to $\lambda_0=-1$).

In particular, I am would like to know how many negative eigenvalues the system has.

Idea: Note that there can be only finitely many negative eigenvalues, since the eigenvalues satisfy $$-\infty <\lambda_0<\lambda_1\leq \dots \to \infty.$$ A theorem (8.3.1) from Coddington-Levinson says that the eigenfunctions $y_{2i+1}$ and $y_{2i+2}$ corresponding to $\lambda_{2i+1},\lambda_{2i+2}$ have precisely $2i+1$ zeros on $[0,1)$. Therefore, if $\lambda =0$ was an eigenvalue, I could count the zeros of the corresponding eigenfunction to determine how many negative eigenvalues there are. So I tried solving $$\frac{d}{dx}\left[\frac{1}{p(x)}\frac{dy}{dx}\right]+\frac{1}{p(x)}(p^2(x)+\frac{1}{2})y=0,$$ but haven't gotten anywhere.

Are there any general results on the number of negative eigenvalues of Sturm-Liouville systems?

In general it's unlikely that $0$ is an eigenvalue.  But you can proceed as follows.  Let $\phi(x,s,\lambda)$ be the solution to the differential equation with
$\phi(0,s,\lambda) = 1$ and $\frac{\partial \phi}{\partial x}(0,s,\lambda) = s$.
Use numerical methods (e.g. bivariate Newton) to find $s$ and $\lambda$ such that $\phi(1,s,\lambda) = 1$ and $\frac{\partial \phi}{\partial x}(1,s,\lambda) = s$.
If you can do so, then $\lambda$ is an eigenvalue and $\phi(\cdot, s, \lambda)$ the corresponding eigenfunction.


TFAE: Completeness Axiom and Monotone Convergence Theorem I'm looking to write a proof that shows

Completeness Axiom / L.U.B. Property of $\mathbb{R}$$\iff$ Monotone Convergence Theorem.

However, it's quite perplexing to me how a proposition about real numbers can imply such an in-depth result about sequences and series.

Could anyone offer me some starting points? I'm thinking by contradiction for $\Leftarrow$, but I have no idea how to do $\Rightarrow$.

"$\Leftarrow$":  Short version: Below is a proof that MCT implies the LUB property.  The basic idea is to take the set $U$ of upper bounds of a nonempty set $A$ that is bounded above, and to construct an increasing sequence $(x_k)$ with no term in $U$, such that $x_k+\varepsilon_k$ is in $U$ for all $k$, and $\varepsilon_k\to 0$.  MCT implies that $(x_k)$ converges, and the limit can be shown to be $\sup A$.  If you are only looking for hints, read no further.

Lemma: MCT $\Rightarrow$ Archimedean Property.
Proof by contradiction: If $\mathbb{N}$ is bounded, then the sequence $(n)_n=(1,2,3,4,\ldots)$ converges by hypothesis to some real number $x$, and then $(n+1)_n$ converges to $x$ and to $x+1$, a contradiction.$\square$

Let $A$ be a nonempty set of real numbers that is bounded above, and let $U$ be the set of upper bounds of $A$.

Claim 1: For all $\varepsilon>0$, $U-\varepsilon:=\{u-\varepsilon:u\in U\}$ is not contained in $U$.
Proof by contradiction: Let $\varepsilon>0$.  If $U-\varepsilon\subseteq U$, then $U-n\varepsilon\subseteq U$ for all $n$.  There exists $u\in U$, and $U$ therefore contains the ray $\{x:x>u\}$.  This implies by the Archimedean property that $\mathbb R=\bigcup\limits_{n=1}^\infty (U-n\varepsilon)\subseteq U$, which contradicts $A\neq\emptyset$.$\square$
Claim 2: $\bigcap\limits_{n=1}^\infty\left(U-\frac{1}{n}\right)\subseteq U$.
Proof: Suppose that $x$ is in $\bigcap\limits_{n=1}^\infty\left(U-\frac{1}{n}\right)$, and that $y>x$.  By the Archimedean property there exists $n\in\mathbb N$ such that $x+\frac{1}{n}<y$.  But $x+\frac{1}{n}$ is in $U$, so this implies that $y$ is not in $A$.  Since $y$ was arbitrary, $x$ is an upper bound for $A$.$\square$

Let $x_1$ be an element of $(U-1)\setminus U$ (which is nonempty by Claim 1).  Since $x_1$ is not in $U$, by Claim 2 there exists $n_1>1$ such that $x_1$ is not in $U-\frac{1}{n_1}$.  Let $x_2$ be an element of $\left(U-\frac{1}{n_1}\right)\setminus U$.  There exists $n_2>n_1$ such that $x_2$ is not in $U-\frac{1}{n_2}$, and we can take $x_3\in \left(U-\frac{1}{n_2}\right)\setminus U$; and so on.  This yields an increasing sequence of positive integers $1=n_0<n_1<n_2<n_3<\cdots$ and an increasing sequence of real numbers $(x_k)$ such that $x_k$ is in $\left(U-\frac{1}{n_{k-1}}\right)\setminus U$.  Then $(x_k)$ is bounded above by each element of $U$.  Assuming MCT, $(x_k)$ converges to some real number $x$.  Since $(x_k)$ is bounded above by each element of $U$ and $\lim x_k=x$, $x$ is less than or equal to each element of $U$.  Since $x\geq x_k$ for all $k$, $x$ is in $\bigcap\limits_{j=1}^\infty\left(U-\frac{1}{n_j}\right)=\bigcap\limits_{n=1}^\infty\left(U-\frac{1}{n}\right)\subseteq U$.  Therefore $x$ is the smallest element of $U$, which means $x=\sup A$.$\square$

Here's an attempt at a proof:

Proposition: Completeness Axiom $\iff$ Monotone Convergence Theorem

Proof:

$\Leftarrow$

Assume for contradiction that Completeness Axiom $\not\Leftarrow$ MCT. That is, $x_n$ is monotone increasing and bounded sequence of real numbers with a finite limit. By our assumption, $\displaystyle\lim_{n \to \infty} x_n = u > \text{sup }x_n$. However, this is a direct contradiction of the Monotone Convergence Theorem since a monotone sequence converges to sup $a_k$ if $a_k$ is increasing. Therefore, the Completeness axiom $\Leftarrow$ Monotone Convergence Theorem

$\Rightarrow$

Suppose that the sequence $x_n$ is monotone increasing and bounded. Then $x_n$ is bounded, so it has a least upper bound $u \equiv \text{sup }x_n$ by the completeness axiom. Now for every $\epsilon > 0$, there exists an $N$ such that $N > u - \epsilon$, since otherwise $u- \epsilon$ is an upper bound of $x_n$, which contradicts to $u$ being the supremum $x_n$. Then, since $x_n$ is increasing, for all $n>N$ we have $| c - x_n | = c - x_n \leq c - x_N < \epsilon$. Hence by definition, the limit of $x_n = u$. Therefore, the Completeness axiom $\Rightarrow$ Monotone Convergence Theorem


What is the definition of an ordinary smooth function? Can't find it anywhere. According to the textbook, PDE's by olver, the dirac delta function represents a unit impulse concentrated along a single point, and is a limit of a sequence of ordinary smooth functions which represent progressively more and more concentrated unit forces. These are the two properties of the delta function, $\delta _{\xi}(x)=0$ for $x\neq \xi$ and $\int_{a}^{b} \delta _{\xi}(x)=1$ for $a<\xi <b$, and the limit function also satisfies the two properties given that $\lim_{n\to\infty}g_{n}(x)=\delta _{\xi}(x)$. This characterization of the impulse force should help in solving linear boundary value problems governed by ODE's on an interval $a<x<b$

Smooth usually means that all derivatives of the function exist and are continuous at all points in the domain (though sometimes definitions vary). Ordinary has no technical meaning here. This line in the book is not meant to be technical--I will attempt below to explain what Peter is getting at.

The "delta function" is not a function in the usual sense (i.e., a rule assigning to each $x$ a real number $f(x)$). If it were, then any reasonable theory of integration (e.g., Riemann or Lebesgue integral) would require the integral of the delta function to be zero (since it is zero at all but one point). The delta function is a "generalized function" or "distribution", and is defined by how it acts on other functions.

The point Peter is making is that even though the delta function is this strange generalized function, it is in fact not too strange because you can express it as the limit (in some sense) of ordinary functions. By ordinary, we mean a rule assigning to each $x$ a real number $f(x)$, so not a distribution or generalized function. The sequence of functions should integrate to 1, and become more and more concentrated around the origin in the limit. There are an infinity of ways of expressing the delta function as the limit of a sequence of ordinary functions. In particular the functions need not be smooth. For example, the sequence of discontinuous functions

$$f_n(x)=\begin{cases}
n,&\text{if }0 \leq x \leq \frac{1}{n}\\
0,&\text{otherwise}\end{cases}$$

converges to the delta function. Hope this helps.

A function $f$ is an ordinary smooth function if $f'$ is defined and continuous on the domain.


Joint probability distribution of X and Y using a table, where Suppose two 4 sided dices are rolled. X is the sum of two resulting numbers after rolling the dice. Y is the absolute difference of two resulting numbers after rolling the dice.

X sample set is {2,3,4,5,6,7,8}
and Y sample set is {0,1,2,3}

I have calculated the values of X which are :
F(2) = [(1,1)] = 1/16
F(3) = [(1,2), (2,1)] = 2/16
F(4) = [(1,3), (2,2), (3,1)] = 3/16
F(5) = 4/16
F(6) = 3/16
F(7) = 2/16
F(8) = 1/16

For Y following are the values:
F(0) = [(1,1),(2,2),(3,3),(4,4)] = 4/16
F(1) = 6/16
F(2) = 4/16
F(3) = 2/16

Please help me in finding joint probability distribution of X and Y using a table. I am confused which values shall I consider?

Comment not answer. I am doing this for six-sided dice. In order to give you an informal view of the joint distribution
of $X$ and $Y,$ I did a simulation (in R) of 10,000 performances of the two-die experiment.

In the figure below the probabilities are at the centers of the squares.
Points are 'jittered' (randomly displaced) in order to give a clue the relative
frequency with which each $(x,y)$ value occurs. The six points (smeared into squares) at the bottom are less likely than the others.

m = 10^4
a = sample(1:6, m, rep=T);  b = sample(1:6, m, rep=T)
x = a+b;  y = abs(a-b)
jx = runif(m, -.4, .4);  jy = runif(m, -.4, .4) # jittering
plot(x+jx, y+jy, pch=".")
  abline(v=2:12, col="green2")
  abline(h=0:5, col="green2")

The probability of each point is a multiple of $1/36.$


Why study linear algebra? Simply as the title says. I've done some research, but still haven't arrived at an answer I am satisfied with. I know the answer varies in different fields, but in general, why would someone study linear algebra?

Linear algebra is vital in multiple areas of science in general. Because linear equations are so easy to solve, practically every area of modern science contains models where equations are approximated by linear equations (using Taylor expansion arguments) and solving for the system helps the theory develop. Beginning to make a list wouldn't even be relevant ; you and I have no idea how people abuse of the power of linear algebra to approximate solutions to equations. Since in most cases, solving equations is a synonym of solving a practical problem, this can be VERY useful. Just for this reason, linear algebra has a reason to exist, and it is enough reason for any scientific to know linear algebra.

More specifically, in mathematics, linear algebra has, of course, its use in abstract algebra ; vector spaces arise in many different areas of algebra such as group theory, ring theory, module theory, representation theory, Galois theory, and much more. Understanding the tools of linear algebra gives one the ability to understand those theories better, and some theorems of linear algebra require also an understanding of those theories ; they are linked in many different intrinsic ways.

Outside of algebra, a big part of analysis, called functional analysis, is actually the infinite-dimensional version of linear algebra. In infinite dimension, most of the finite-dimension theorems break down in a very interesting way ; some of our intuition is preserved, but most of it breaks down. Of course, none of the algebraic intuition goes away, but most of the analytic part does ; closed balls are never compact, norms are not always equivalent, and the structure of the space changes a lot depending on the norm you use. Hence even for someone studying analysis, understanding linear algebra is vital.

In other words, if you wanna start thinking, learn how to think straight (linear) first. =)

Hope that helps,

I was browsing the posts flaired Mathematics at r/askscience, and lighted upon the same question!

I'll replicate simply the top-voted post and its top-voted follow-up comment.

AirborneRodent

Let me give a concrete example.  I use linear algebra every day for my job, which entails using finite element analysis for engineering.

Imagine a beam.  Just an I-beam, anchored at one end and jutting out into space.  How will it respond if you put a force at the end?  What will be the stresses inside the beam, and how far will it deflect from its original shape?

Easy.  We have equations for that.  A straight, simple I-beam is trivial to compute.

But now, what if you don't have a straight, simple I-beam? What if your I-beam juts out from its anchor, curves left, then curves back right and forms an S-shape?  How would that respond to a force?  Well, we don't have an equation for that.  I mean, we could, if some graduate student wanted to spend years analyzing the behavior of S-curved I-beams and condensing that behavior into an equation.

We have something better instead: linear algebra.  We have equations for a straight beam, not an S-curved beam.  So we slice that one S-curved beam into 1000 straight beams strung together end-to-end, 1000 finite elements.  So beam 1 is anchored to the ground, and juts forward 1/1000th of the total length until it meets beam 2.  Beam 2 hangs between beam 1 and beam 3, beam 3 hangs between beam 2 and beam 4, and so on and so on.  Each one of these 1000 tiny beams is a straight I-beam, so each can be solved using the simple, easy equations from above.  And how do you solve 1000 simultaneous equations?  Linear algebra, of course!

MiffedMouse

And to be clear, this kind of situation shows up everywhere.

Atomic orbitals? Check

Fluid flow? Check

Antenna radiation patterns? Check

Face recognition? Check

Honestly, anything that involves more than one simple element probably uses linear algebra.


Is there a $\mathbb{C}$ vector space structure over $\mathbb{R}$ with scalar multiplication as defined? To find is a $\mathbb{C}$ vector space structure over $\mathbb{R}$ with addition and scalar multiplication such that scalar multiplication has the following property:

$\cdot : \mathbb{C} \times \mathbb{R} \rightarrow \mathbb{R}$ s.t.

$\cdot : \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ is a usual multiplication
 in $\mathbb{R}$

No. For any vector space $V$, any nonzero vector $v$, and any scalars $k$ and $l$, $kv=lv$ implies that $k=l$. Here, $kv$ already takes all possible values when $k$ ranges over $\Bbb R$, so there's nothing for (say) $iv$ to be.

This supposed vector space would be $1-$dimensional. Let $\{a\}$ be a basis. Then $i\cdot a = r =\frac{r}{a}\cdot a , \ \ r \in \mathbb{R}$ ↯.


Multiplying a matrix with its eigenvectors stretches or contracts the vector without changing its "direction". Is this true for complex eigenvalues? I tried to prove this as follows -
Suppose A is a square matrix with a complex eigenvalue $\lambda$ and its corresponding eigenvector x.

Then, by definition
Ax = $\lambda$x

Angle between x and the transformed vector $\lambda$x is given by

cos$\theta$ = $\dfrac{<\textbf{x},\lambda\textbf{x}>}{\parallel \textbf{x}\parallel\parallel\lambda\textbf{x}\parallel}$

$\Rightarrow$  cos$\theta$ = $\dfrac{\overline{\lambda}<\textbf{x},\textbf{x}>}{|\lambda|\parallel \textbf{x}\parallel\parallel\textbf{x}\parallel}$

$\Rightarrow$  cos$\theta$ = $\dfrac{\overline{\lambda}<\textbf{x},\textbf{x}>}{|\lambda|\parallel\textbf{x}\parallel^2}$

Now, $\parallel\textbf{x}\parallel^2 = <\textbf{x},\textbf{x}>$

So I get,

cos$\theta$ = $\dfrac{\overline{\lambda}}{|\lambda|}$

where $\parallel\textbf{x}\parallel$ represents the norm of vector x and $<\textbf{x},\textbf{y}>$ is the inner product of two vectors x and y

The value of cos$\theta$ should have come out to be 1 or -1 but this is not the case here. Also, how is the cosine of the angle coming out to be a complex number? Should I take the absolute value of the inner product ?

This question is similar to the question about roots of polynomials. Suppose you have a quadratic equation $\, ax^2 + bx + c = 0 \,$ with real coefficients. If there are two real roots, then the polynomial factors into two linear factors. What if there are two conjugate complex roots? The two factors are not real but complex. We were expecting real roots, but then the actual roots are complex.

A similar situation arises with a two dimensional real vector space with a linear map given by a $\, 2\times 2\,$ matrix. The eigenvector equation leads to solving a quadratic. If the two roots are real then we can find the eigenvectors that go along with those eigenvalues. If the roots are two conjugate complex roots, then what? Can we multiply vectors in a real vector space by a complex scalar?

Maybe. For example, if the map is rotation by an angle then the eigenvalue is a unit complex number corresponding to that angle. Given a standard orthonormal basis for the space, define the scalar multiplication by $\,i\,$ to take the first basis vector to the second and that second vector to the negative of the first. Now we have a one dimensional complex vector space.

If you are asking about a complex vector space, then according to the Wikipedia article inner product space, your formula should be modified to read
 $\, \cos\theta=\dfrac{|\langle\textbf{x},\lambda\textbf{x}\rangle|}{\parallel \textbf{x}\!\parallel\,\parallel\!\lambda\textbf{x}\parallel}.\,$ The final result is now $\, \cos\theta = |\overline\lambda| / |\lambda| = 1\,$ and the angle $\, \theta \,$ is $0.\,$ This means that $\, \lambda\textbf{x} \,$ is in the same "direction" as $\, \textbf{x} \,$ in a complex vector space. What this means is that the usual ideas we have about "direction" and angles in real vector spaces must be greatly modified when applied to complex vector spaces.


ODE problem $\frac{dB}{B(a+\frac{\sigma^2}{2} B)}=-dt$ I am analyzing solution to a problem where one of the steps was solving the below ODE, I have the final form of this equation but I cannot follow the transitions which were done.

Can anybody explain how this equation was solved?

$$\frac{dB}{B(a+\frac{\sigma^2}{2} B)}=-dt$$

which should result in
$$ \frac{B}{a+\frac{\sigma^2}{2} B}=ce^{-at}$$

Using Partial Fractions,
$$ \frac{1}{B(a+\frac{\sigma^2B}{2})} = \frac{A}{B} + \frac{C}{a+\frac{\sigma^2B}{2}} $$
$$ \therefore Aa = 1, A = \frac{1}{a}  $$
$$ A\frac{\sigma^2}{2} + C = 0, C = -A\frac{\sigma^2}{2} = -\frac{\sigma^2}{2a}  $$
$$ \frac{1}{B(a+\frac{\sigma^2B}{2})} = \frac{1}{aB} + \frac{-\sigma^2}{(a+\frac{\sigma^2B}{2})2a} $$
$$ \int\frac{1}{B(a+\frac{\sigma^2B}{2})} dB = \int \frac{1}{aB} + \frac{-\sigma^2}{(a+\frac{\sigma^2B}{2})2a} dB = \frac{\ln{B}}{a} -\frac{\ln(a+\frac{\sigma^2B}{2})}{a} $$
$$ \int\frac{1}{B(a+\frac{\sigma^2B}{2})} dB = \frac{1}{a}\ln(\frac{B}{a+\frac{\sigma^2B}{2}}) = \int -dt = -t + k $$
where $k$ is an integration constant
$$ \therefore \frac{B}{a+\frac{\sigma^2B}{2}} = e^{-at}.e^{ak} = ce^{-at} $$
where $c = e^{ak}$ is some constant.

We have: $$\frac{dB}{B(a+\frac{\sigma^2}{2} B)}=-dt$$

Grouping: $$\frac{dt}{dB}=-\frac{1}{B(a+\frac{\sigma^2}{2}B)}$$

Then use partial fraction and integrate both sides.


Can the given vector be expressed as a linear combination of the other three Four vectors from $\mathbb{R}^4$ are given:
$$v_1 = (1, -2, 0, 1), v_2 = (0, 1, -1, -3), v_3 = (1, 0, -2, -5), v_4 = (-3, 5, 1, 0)$$
Can the vector $v_4$ be expressed as a linear combination of the other three? The solution given is yes: $$v_4 = av_1 + (2a + 5)v_2 + (-a - 3)v_3 \qquad a ∈ \mathbb{R}$$
I tried to solve the system of linear equations $\alpha v_1 + \beta v_2 + \gamma v_3 = a v_4$, but this seems to get me nowhere. How can I express $v_4$ as a linear combination of the other three?

The general solution is:

$$ av_1+(5+2a)v_2+(-3-a) v_3 = v_4$$

for any $a \in \mathbb{R}$, as stated. Here's why...

Firstly write $\alpha v_1+\beta v_2+\gamma v_3 = v_4$ out as

$$
\left(\begin{matrix}\alpha+\gamma \\-2\alpha+\beta \\-\beta-2\gamma \\ \alpha-3\beta-5\gamma\end{matrix}\right) =
\left(\begin{matrix}-3 \\5 \\1 \\ 0\end{matrix}\right)
$$

(I've obviously swapped your row vectors for column vectors.)

If a solution exists for the whole vector, then a solution must exist for its first three elements, so we might as well just work with the following to start with:

$$
\left(\begin{matrix}\alpha+\gamma \\-2\alpha+\beta \\-\beta-2\gamma \\\end{matrix}\right) =
\left(\begin{matrix}-3 \\5 \\1 \end{matrix}\right)
$$

Re-writing this as a matrix equation, we have:

$$
\left(\begin{matrix}1 & 0 & 1 \\-2 & 1 & 0 \\0 & -1 & -2 \\\end{matrix}\right)
\left(\begin{matrix}\alpha \\ \beta \\ \gamma \\\end{matrix}\right) =
\left(\begin{matrix}-3 \\5 \\1 \end{matrix}\right)
$$

The determinant of the matrix here is $0$, so we may put $\alpha=a$ where $a \in \mathbb{R}$ is an arbitrary constant. Continuing to solve, we find $\beta=5+2a$ and $\gamma=-3-a$. These values also work to make $\alpha-3\beta-5\gamma=0$ (the fourth element of the original vector equation), so we have the solution!

In your set: $\;v_4\;$ is a linear combination of the other three vectors iff when we form the corresponding matrix with $\;v_4\;$ the last row and we reduce it by rows, this last row becomes all zeros (why?! This must be clear in order to be sure what is going on here...):

$$\begin{pmatrix}
1&-2&0&1\\
0&1&-1&-3\\
1&0&-2&-5\\
-3&5&1&0
\end{pmatrix}\longrightarrow\begin{pmatrix}
1&-2&0&1\\
0&1&-1&-3\\
0&2&-2&-6\\
0&-1&1&3
\end{pmatrix}$$

...and we're done as we can see the last row is the third one multiplied by $\;-\frac12\;$ .


Permutation query involving 3 people with a limit of 45 as the sum. I'm looking to find all the combinations of numbers possible in the below example. I shall do my very best to explain the situation clearly as I'm not too sure how to derive this outcome myself. Thanks in advance.

I'm looking to have this in spreadsheet format since it will be a long list (from research it seems possible for their to be a function in a spreadsheet that can do this. If I only knew how I would do it myself!

There are 3 people. The sum of numbers between these 3 people can only equal 45 in total no more.

An example of an outcome would be something like this:

30,5,10

5,10,30

10,30,5

10,5,30

30,10,5

5,30,10

I want to extend this simplified example to show all the outcomes possible. Only conditions are that the numbers combined can't exceed 45. 0 is not considered.

Kind regards,

Harvey :)

*Also if anyone can explain how to do this in a spreadsheet I will be very grateful.

What you are looking for would be something along the lines of $ 0 < x_0 \leq 43, 0 < x_1 \leq 44-x_0, 0 < x_2 \leq 45-(x_0 + x_1)$ where $x_0, x_1, x_1 \in \Bbb N$.

There would be $n-1 \choose k-1$ combinations for writing non-zero positive integral solutions of
$x_1+x_2+.......x_k = n$


When is round-robin scheduling possible and with in minimal time? Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five weeks?

A naive attempt fails:

$$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$
$$(x_0,x_2), (x_1, x_3) .. oops$$

Some care is needed to get this to work. A solution:

$$(x_0,x_3), (x_1, x_5), (x_2, x_4)$$
$$(x_1,x_4), (x_2, x_0), (x_3, x_5)$$
$$(x_2,x_5), (x_3, x_1), (x_4, x_6)$$
$$(x_0,x_1), (x_2, x_3), (x_4, x_5)$$
$$(x_0,x_5), (x_2, x_1), (x_4, x_3)$$

This solution certainly is not easy to generalize. Questions:

Is this in fact always possible for an even number of teams?
Is there a convenient algorithm for producing the schedule?
Can this problem be easily expressed in terms of graph theory, combinatorics, or abstract algebra?

Here's an easy way for $2n \geq 6$.

Construct the regular polygon with $2n$ vertices. Label the vertices $x_1$ to $x_{2n}$. Take any edge that is not of the form $x_i, x_{i+n}$. Consider all edges that are parallel to it, and label them as 1 day of games. Rotate around the polygon and you are done.

For odd number of teams $2n+1 \geq5 $, show that you need $2n+1$ days. Repeat the above construction, taking note that you miss out 1 team each day.

If you read Ross's answer, you will see that this expresses the same idea.

Let me explain the algorithm with 6 teams. You start

x1 vs x2

x3 vs x4

x5 vs x6

Then you keep x1 fixed and move the other teams (counter-)clockwise

x1 vs x4

x2 vs x6

x3 vs x5

and proceed doing this until every team has played against each other. For an odd number of teams you define x1 to be the bye.

x1 vs x6

x4 vs x5

x2 vs x3

then

x1 vs x5

x6 vs x3

x4 vs x2

and finally

x1 vs x3

x5 vs x2

x6 vs x4


A conjecture from Cauchy–Schwarz inequality we know the Cauchy–Schwarz inequality in $R^3$:

$$(x_1^2+x_2^2+x_3^2)(y_1^2+y_2^2+y_3^2)\geq(x_1y_1+x_2y_2+x_3y_3)^2$$

$$(x_1+x_2+x_3)(y_1+y_2+y_3)\geq(\sqrt{x_1y_1}+\sqrt{x_2y_2}+\sqrt{x_3y_3})^2$$

i guess the following inequlity exists too:

$$(x_1+x_2+x_3)(y_1+y_2+y_3)(z_1+z_2+z_3)\geq(\sqrt[3]{x_1y_1z_1}+\sqrt[3]{x_2y_2z_2}+\sqrt[3]{x_3y_3z_3})^3$$

is it true? how to prove?

Lets look at a simple proof of Cauchy Schwarz inequality and see if we can extend in the direction you want.

Let $A^2 = \sum_{i=1}^n {a_i ^2}, \quad B^2 = \sum_{i=1}^n  {b_i^2}$

Then $\sum_{i=1}^n  \dfrac{a_i b_i}{AB} \le \sum_{i=1}^n \dfrac{1}{2}\left( \dfrac{a_i^2}{A^2} + \dfrac{b_i^2}{B^2} \right) = 1$
So $\sum_{i=1}^n  {a_i b_i} \le AB$, or if you prefer $ A^2 B^2 \ge \left(\sum_{i=1}^n  {a_i b_i} \right)^2$ which is Cauchy Schwarz.

Extending this, we have:

Let $A^3 = \sum_{i=1}^n {a_i ^3}, \quad B^3 = \sum_{i=1}^n  {b_i^3}, \quad C^3 = \sum_{i=1}^n  {c_i^3}$

Then $\sum_{i=1}^n  \dfrac{a_i b_i c_i}{ABC} \le \sum_{i=1}^n \dfrac{1}{3} \left( \dfrac{a_i^3}{A^3} + \dfrac{b_i^3}{B^3} + \dfrac{c_i^3}{C^3} \right) = 1$

So $\sum_{i=1}^n  {a_i b_i c_i} \le ABC$, or if you prefer, $A^3B^3C^3 \ge \left(\sum_{i=1}^n  {a_i b_i c_i} \right)^3$ is the extended version.  Essentially your RHS needs to be cubed, not squared.


Does there exist a monotonically decreasing function that is its own derivative? I know that $f(x) = e^x$ is its own derivative. It is a monotonically increasing function. It seems intuitively plausible to me that there might be a monotonically decreasing function with the same property. Does one exist?

$f(x) = -ce^x, c > 0$
This isn't a particularly exciting answer, but it is the correct one. All functions that are their own derivatives are of the form $f(x) = ce^x, c \in \mathbb{R}$, as explained in this question: Prove that $C\exp(x)$ is the only set of functions for which $f(x) = f'(x)$

The requirement yields the differential equation dy - ydx = 0, which has the only solutions y =  kexp(x), where k is an arbitrary constant, and f(x) = 0 for all x in the domain. Now f(x) = 0 is decreasing and if k < 0,  kexp(x) is a decreasing function. and these are the only collection of functions for which f’(x) = f(x) with f(x) decreasing.


Identity for Landau symbols (little $o$) I was wondering if the following is true:

If $f=g+o(x)$, then $o(f)=o(g)$.

Here, $f=f(x)$, $g=g(x)$.

No, this is not true.
With the remark that it's usually a very good idea to specify where the asymptotics are taken (i.e., the point $a\in [-\infty,\infty]$).

Now, take $f,g$ defined on $\mathbb{R}$ by $f(x)=x^2$ and $g(x)=x^4$. Consider the asymptotics at $0$: certainly,
$$
f(x) = g(x) + o(x)
$$
as desired. Yet, we do have $x^3 = o(f(x))$ (at $0$, but definitely not $x^3=o(g(x))$.

The writing ''$o(f)=o(g)$'' does not make any sense: the symbol "little o" is not defined like an operator on functions, but only as $f(x)=o(g(x))$ for $x\rightarrow x_0$, meaning that the quotient of $f$ by $g$ has limit zero as $x\rightarrow x_0$, and that is it. So your equality does not make any sense.

To be more precise, and to clarify something which is not completely clear in the book, something that people often overlook, or simply do not know at all is that, from a logical point of view, when we define $f(x)=o(g(x))$in Mathematics what is defined it is not really the symbol ''$o$'', but the symbol ''$=o$'', and this is the reason why equations of the kind you wrote simply do not make sense.

The same thing is true for all the other ''order of growth'' symbols like $O$, $\sim$, etc. What we define are not these symbols per se, but the notions ''$=O $ '', ''$=\Theta$'', and so on.


Is the set of sum over a diagram is uncountable set? Consider the following diagram:
Let $0<x<\frac{1}{2}$

Note that $[.]$ is not box function
It is easy to see that $1$ split into $x$ and $(1-x)$. In next stage $x$ split into $x^2$ and $x(1-x)$ and $(1-x)$ split into $x(1-x)$ and $(1-x)^2$. Note that I do not write $x(1-x)$ twice, instead of that in this stage we have three values $x^2,x(1-x),(1-x)^2$. Continue this process in the next stage (see the diagram for more detail)
Now comes the important part:
Add take $1$ first. Then add either $x$ or $(1-x)$. If you added $x$ then next add either $x^2$ or $x(1-x)$ and if you added $(1-x)$ then up next add either $x(1-x)$ or $x^2$. Continue this process again.
For example you will get a value $1+\sum_{n=1}^{\infty}x^n$. Another one could be $1+\sum_{n=1}^{\infty}x(1-x)^{n-1}$. It depends on which path you choose. Every zigzag path will give you a $\color{red}{\text{different sums}}$.
$\color{red}{\text{different sums}}$ means sum over different zigzag path. Note that $\color{red}{\text{different sums}}$ does not mean two different path always give different values.
$\large{F}$or example $1+(1-x)\sum_{n=0}^{\infty}x^n$ and $1+x\sum_{n=0}^{\infty}(1-x)^n$ are two $\color{red}{\text{different sums}}$ but they yeilds same value $2$ i.e. $1+(1-x)\sum_{n=0}^{\infty}x^n=1+x\sum_{n=0}^{\infty}(1-x)^n=2$
Let say $T_x=\{\text{set of all $\color{red}{\text{different sums}}$ for a given $x$ }\}$
It can be easily seen there is uncountable number of $\color{red}{\text{different sums}}$.

Question: is there uncountable number of distinct elements in $T_x$ for a given $x$?

Observation:

It can be easily seen that minimum element of $T_x$ is $\frac{1}{1-x}$ and maximum element of $T_x$ is $\frac{1}{x}$.

$2\in T_x$ for every $x\in \Big(0,\frac{1}{2}\Big)$

But I could not find a way to prove or disprove uncountability. Any help would be appreciable.
$\blacksquare\space\space\blacksquare\space\space\blacksquare\space\space$ Thanks to MANMAID I am attaching a new diagram:
Let $0<x<1$

Formalization

For $n \in \mathbb{N}$ let $\{ 0, 1 \}^n$ denote the set of $n$-element binary sequences, i.e. the set of functions $f : \{ 0, 1, \ldots, n-1 \} \to \{ 0, 1 \}$.
Let $\{ 0, 1 \}^{\mathbb{N}}$ denote the set of infinite binary sequences, i.e. the set of functions $s : \mathbb{N} \to \{ 0, 1 \}$.
For $s \in \{ 0, 1 \}^{\mathbb{N}}$ and $n \in \mathbb{N}$ (or $s \in \{ 0, 1 \}^m$ and $n \leqslant m$ respectively) by $s \upharpoonright n$ we denote the preffix of $s$ of length $n$, i.e. the restriction $s \upharpoonright \{ 0, 1, \ldots, n-1 \}$.
For $f \in \{ 0, 1 \}^n$ let $\alpha(f) = \# \{ k < n : f(k) = 0 \}$ and $\beta(s) = \# \{ k < n : f(k) = 1 \}$ (the number of zeros and ones in $f$ respectively).

Note that any path in the diagram can be represented by an infinite binary sequence, so we may think of $\{ 0, 1 \}^{\mathbb{N}}$ as the set of all possible paths.

Fix $x \in \left( 0, \frac{1}{2} \right)$ and define $\varphi : \{ 0, 1 \}^{\mathbb{N}} \to \mathbb{R}$ as

$$\varphi(s) = \sum_{n=0}^{\infty} x^{\alpha(s \upharpoonright n)} \cdot (1-x)^{\beta(s \upharpoonright n)}.$$

Thus $\varphi(s)$ clearly represents the sum associated with the path $s$. So the question is: is $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ uncountable?

Solution

On $\{ 0, 1 \}^{\mathbb{N}}$ there is a natural lexicographical order, given by $$s \prec t \iff (\exists n \in \mathbb{N}) \big[ s \upharpoonright n = t \upharpoonright n \wedge s(n) < t(n) \big].$$

In words: if $s, t$ are different, find the first position $n \in \mathbb{N}$ on which they differ, so $s(n) \neq t(n)$ and compare them by the value on that position. On your diagram, any two different paths diverge at some point and the one going to the left will be smaller with respect to this ordering.

The key observation is: let $s \prec t$. Then $\varphi(s) \leqslant \varphi(t)$ and $\varphi(s) = \varphi(t)$ if and only if there is $n \in \mathbb{N}$ such that $s$ and $t$ agree up to $n$ and then $s$ continues as $0, 1, 1, 1, \ldots$ and $t$ continues as $1, 0, 0, 0, \ldots$

Proof.

From the definition of $s \prec t$ we have $n$ such that $s$ and $t$ agree up to $n$ (exclusively) and then $0 = s(n) < t(n) = 1$. Let $s^*$ be an infinite sequence defined as $s \upharpoonright n$ followed by $0, 1, 1, 1, \ldots$ Similarly, let $t_*$ start with $t \upharpoonright n$ and continue as $1, 0, 0, 0, \ldots$

Note that for each $k \in \mathbb{N}$ we have $\beta( s \upharpoonright k) \leqslant \beta( s^* \upharpoonright k )$ since $s$ and $s^*$ agree up to $n+1$and then $s^*$ becomes constantly $1$. Therefore $\varphi(s) \leqslant \varphi(s^*)$ since multiplying things by $1-x$ makes them greater than multiplying by $x$. Similarly we prove that $\varphi(t_*) \leqslant \varphi(t)$.

It's also easy to see that if $u, v$ are infinite binary sequences and $f \in \{ 0, 1 \}^m$ is a finite binary sequence such that $u = f \frown v$ (where $\frown$ denotes contatenation), then

if $k < m$, then $\alpha( u \upharpoonright k ) = \alpha( f \upharpoonright k )$ and $\beta( u \upharpoonright k ) = \beta( f \upharpoonright k ),$
for $k \geqslant 0$: $\alpha( u \upharpoonright (m+k) ) = \alpha( f ) + \alpha( v \upharpoonright k )$ and $\beta( u \upharpoonright (m+k) ) = \beta( f ) + \beta( v \upharpoonright k ).$

Hence

$$\varphi(u) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(v).$$

Taking $f$ to be the common preffix of $s$ and $t$, i.e. $f = s \upharpoonright n = t \upharpoonright n$, we obtain

$$\varphi(s^*) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(0, 1, 1, 1, \ldots) \\[1ex]
\varphi(t_*) = \sum_{k=0}^{m-1} x^{\alpha(f \upharpoonright k)} (1-x)^{\beta(f \upharpoonright k)} + x^{\alpha(f)} (1-x)^{\beta(f)} \cdot \varphi(1, 0, 0, 0, \ldots).$$

Computing $\varphi(0, 1, 1, 1, \ldots) = 2 = \varphi(1, 0, 0, 0, \ldots)$ yields $\varphi(s^*) = \varphi(t_*)$, so $\varphi(s) \leqslant \varphi(t)$.

Now if $\varphi(s) = \varphi(t)$, then $\varphi(s) = \varphi(s^*)$ and $\varphi(t_*) = \varphi(t)$, which clearly implies $s = s^*$ and $t = t_*$, so the claim has been proved.

Now let $A \subseteq \{ 0, 1 \}^{\mathbb{N}}$ be the set of all infinite binary sequences eventually stabilizing at $1$. From the above fact, the restriction of $\varphi$ to $\{ 0, 1 \}^{\mathbb{N}} \setminus A$ is strictly increasing, hence injective. But $A$ is countable, so $|\{ 0, 1 \}^{\mathbb{N}} \setminus A| = \mathfrak{c}$, thus $\varphi \left[ \{ 0, 1 \}^{\mathbb{N}} \right]$ has cardinality $\mathfrak{c}$ so in particular is uncountable.

Further insight

In this section I will provide less details and concentrate on how it is rather than why it is true. Hopefully you can fill the gaps if you're interested.

The set $\{ 0, 1 \}^{\mathbb{N}}$ can be regarded as a metric space known as the Cantor set with the metric defined as

$$d( s, t ) = \begin{cases} 0 & \text{if } s = t \\ 2^{-\min \{ n : s(n) \neq t(n) \}} & \text{otherwise} \end{cases}$$

It's not hard to see that the map $\varphi$ is continuous, because if $s, t$ agree up to $n$, i.e. $s = f \frown u$ and $t = f \frown v$ for some $f \in \{ 0, 1 \}^n$ and $u, v$ infinite, then

$$|\varphi(s) - \varphi(t)| = x^{\alpha(f)} (1-x)^{\beta(f)} \cdot |\varphi(u) - \varphi(v)| \leqslant (1-x)^n \cdot \left[ \frac{1}{x} - \frac{1}{1-x} \right]$$

so the difference can be made arbitrarily small by making $n$ large. Now the fact proven above implies that $\varphi = \psi \circ p$ for some continuous $\psi : [0, 1] \to \mathbb{R}$, where $p : \{ 0, 1 \}^{\mathbb{N}} \to [0, 1]$ is the standard continuous surjection

$$p(s) = \sum_{n=0}^{\infty} \frac{s(n)}{2^{n+1}}.$$

Since $\psi$ is continuous, from the Darboux property it is onto $\left[ \frac{1}{1-x}, \frac{1}{x} \right]$, thus so is $\varphi$.
So every number $y \in \left[ \frac{1}{1-x}, \frac{1}{x} \right]$ can be obtained as a sum over a path $s \in \{ 0, 1 \}^{\mathbb{N}}$ which is unique up to the case described by the fact we have proven.

The more usual way to draw this is as a binary tree, so the downward paths do not come to the same vertex.  Then you have one vertex at the root, two at the next level, four at the next, and $2^n$ at level $n$.  As you traverse the tree you add a bit to the binary number that is the sum, $0$ if you take the left fork and $1$ if you take the right.  Then it is clear that you can have any number in $[0,1]$ as the sum, so there are an uncountable number of possible sums.  There are only countably many vertices in the tree, whether it is $1+2+3+4+\ldots$ or $1+2+4+8+\ldots$


Probability of Occurence of HEART or EARTH This is one of the questions I came across and I could only solve it partially. The question went

A man is randomly typing on a keyboard. Then, what is the probability that the word HEART comes before EARTH?

My attempts

The first $4$ letters of EARTH are the same as last 4 of HEART.

For EARTH to appear before HEART, any letter other than H must've appeared first and then should be followed by EART and then a H later on.

For HEART to appear first before EARTH, only the letter H must've appeared first and then may be followed by EART.

Since, the number of letters to appear in the case of HEART is less than EARTH, the probability of occurrence of HEART is more than that of EARTH.

To calculate how much, I'm just considering in case of

EARTH first: $$P(E)=\frac{25}{26}.\frac{1}{26}.\frac{1}{26}.\frac{1}{26}$$

HEART first: $$P(E)=\frac{1}{26}.\frac{25}{26}.\frac{25}{26}.\frac{25}{26}$$

This obviously isn't correct, since it doesn't give any individual probability for the occurrence of each letter.

So, can anyone calculate the probability for each of these two?

You can assume the key options are H, E, A, R, T, X, where "X" represents any other key that is not H, E, A, R, or T.  These are typed with probabilities $a, a, a, a, a, 1-5a$, respectively, for $0< a\leq 1/5$.

Next, you can model the situation with a finite state discrete time Markov chain.  For example, the initial state can be labeled START, there is a trapping state HEART, and another trapping state EARTH.  (A state $i$ is a "trapping state" if $P_{ii}=1$, that is, once reached, the probability of staying there is 1.)

Can you define all states in the state space $S$, draw the chain, and label the transition probabilities?

You then define $p(i)$ as the probability of eventually ending in HEART, given we start in state $i \in S$, and write recursive equations for $p(i)$.  Then the probability we eventually end in HEART is just $p(START)$. Note that $p(HEART) = 1$ and $p(EARTH)=0$.

First some notation - let $E(s)$ denote the expected number of letters that are typed before string $s$ is observed.

Now suppose that $E(HEART) < E(EARTH)$. Letters are typed at random, so we can rename the letters without affecting probabilities. By renaming letters H to E, E to A etc. we can show that $E(EARTH) < E(ARTHE)$. And by applying this argument several time we have

$E(HEART) < E(EARTH) < E(ARTHE) < E(RTHEA) < E(THEAR) < E(HEART)$

which is a contradiction.

If we assume $E(HEART) > E(EARTH)$ we can also derive a contradiction. So the only possible conclusion is $E(HEART) = E(EARTH)$ and so the probability that HEART is observed before EARTH is 0.5.

(This is essentially a symmetry argument).


Isomorphism between groups with same presentation So say I have two groups $G$ and $H$. We let $G = \langle X \mid R\rangle$ and $H = \langle Y \mid R'\rangle$ where $|X| = |Y|$ and $R$ and $R'$ are the "same" relations. (For example if $(ab)^c = e$ is a relation in $R$ then there is the same relation in $R'$ aka there exists a relation $(a'b')^{c'} = e$.)

It seems that we should be able to define a simple isomorphism between $G$ and $H$ where each generator in $X$ gets sent to the appropriate generator in $Y$ such that all relations match up. I've been told that this map only gives us surjection which seems confusing as theoretically it should be inversable and thus be an isomorphism.

My question: Is it true that we only have a surjection in the case of a map

$$ \phi \colon G \rightarrow H$$

or can we actually show an isomorphism by identifying the appropriate generators together? If we don't have isomorphism, why is that?

If you define a map $G \to H$ with $\phi(a) = a'$  then it is clearly an isomorphism. Indeed if a combination of elements of $X$ belongs to $\ker f$ then   its image has to be identity in $H$.


How to solve for $x$ algebraically, given that $x^2 = 4- \sqrt{12}$ This is a question I have been chewing on for a couple days but haven't quite solved yet. The value of $x^2$ is given as $4-\sqrt{12}$ and then the result given as $±( 1-\sqrt{3})$. How would I solve this problem algebraically without prior knowledge of the answer?

Solution to a problem

Given an expression like $\sqrt{a\pm\sqrt{b}}$, can we simplify it to an expression of the form $\left|c\pm\sqrt{d}\right|$?

Well, suppose we could.  Then we would find that

$$
(c\pm\sqrt{d})^2 = a\pm\sqrt{b}
$$

Carrying out the square, we get

$$
c^2+d\pm2\sqrt{4c^2d} = a\pm\sqrt{b}
$$

We might therefore try to equate $c^2+d$ with $a$, and $c^2d$ with $b/4$.  In this case, we have $a = 4$ and $b = 12$.  Can we find two numbers whose sum is $4$, and whose product is $12/4 = 3$?  The obvious answer is $1$ and $3$, and in this case, $1$ is a perfect square, so it makes a good choice for $c^2$.  Then $d = 3$, and we have

$$
\sqrt{4-\sqrt{12}} = \left|1-\sqrt{3}\right| = \sqrt{3}-1
$$

Since the value desired is not restricted to the positive value, then $1-\sqrt{3}$ will also work.  (We could also have had $c = -1$, but that just yields $-1+\sqrt{3}$ again.)

If you want an algorithmic way of finding two values whose sum is $s$ and whose product is $p$, note that these two values are the roots to the quadratic equation

$$
x^2-sx+p = 0
$$

Solve for the roots, and $c^2$ can be any positive root, if one exists, and $d$ is then the other root.

$$x^2=4-\sqrt{12}$$
Rewrite the square root:
$$x^2=4-\sqrt{4\cdot3}$$
$$x^2=4-2\sqrt{3}$$
Rewrite (using binomial formula):
$$x^2=3-2\sqrt{3}+1=(\sqrt{3}-1)^2$$
Take square root:
$$x_1=(\sqrt{3}-1)$$
$$x_2=(1-\sqrt{3})$$

In general you should first look for square roots with non-squarefree radicals, because you can always factor out the square number.
Also if you take the square root of a sum try rewriting it as a product (binomial formula).


Having a graph of complaints with 10% of enemies, prove that you always may arrest more enemies than honest people Not more than 10% of people of some country are enemies. Each man knows less than 500 other people. Each honest man tells to the dictator about one enemy he knows, and each enemy tells about a random man.

Prove that the dictator is able to arrest such a set of people that strictly more than 50% of them would be enemies.

The easy thing is to arrest exactly 50%. We know that the graph definitely has the cycle, and each cycle 50% consists of enemies. The graph consists of cycles and trees, that enters the cycles.

I've tried 2 strategies: to take 10% of people with the biggest amount of votes, and to take the smallest group with at least 10% of votes. None of this helps, but it seems that I need some compromise between these strategies, though I'm not sure about it.

UPD: There should be strict proof for any number of people in the country. But I guess the most important case is when there is very big amount of people.

UPD 2: If we know that every honest man tells about one enemy, we can deduce that every man knows at least one enemy.

The strategy is intricated, and it doesn't suffice to count how many times each person has been voted to be an enemy.

First we fix some notations.

Let $N$ be the number of people in the country $X$. The honest man can receive only fake votes
and so there are at most $N/10$ fake votes given. Let $F\subset X$ be the subset of people that receive at least one vote (fake or not).
We know that $f=\# F$ is at most $\frac{2N}{10}$, the sum of the fake votes and the number of enemies (who can receive "true" votes).

The proposition P5 proves that the dictator can determine a set with (strictly) more enemies than honest man (Proposition P1 and P4 are needed to prove P5, but Propositions P2 and P3 are just for
illustration).

The number 500 is used under the assumption that "knowing someone" is symmetric and so each person can receive at most 500 votes (of all people that he knows). It is used in P2 and in
P5.

${\bf P1:}$ If there is a subset $M$ of $m$ persons such that all the people in $M$ together receive $n$ votes from which at most $r$ are fake votes,
then one of the following holds (maybe the two are true):

1) there are more enemies than honest people in the set $M$, and the dictator is able to know it, or

2) there is a subset $M_1$ of $M$ with $\lfloor\frac m2 \rfloor$
people such that all the people together in $M_1$ receive at least $n-r$ votes and at most $r$ fake votes.

The same is true if we know that $M$ receives a set of $n$ votes from which at most $r$ are fake votes.

${\bf P2:}$ If $f\le N/10$, then the dictator has a strategy in order to determine a set with more enemies than honest man in it, by knowing only how many votes (fake or not) each person receives.

${\bf P3:}$ There is a distribution of votes in a country, such that for the dictator it is impossible to determine
a set with more enemies than honest man in it, if he knows only the distribution of votes.

${\bf P4:}$ There exists a set $G$ of people (which can be known by the dictator), with $F\subset G\subset X$, such that the number of enemies in $G$ is greater than or equal to the number of honest man in $G$.

${\bf P5:}$ The dictator is able to determine a set with more enemies than honest man, by knowing how many votes of the set $X\setminus G$ each person receives.

${\bf Proof\ of\ P1:}$
Order the people in $M$ with increasing order of votes received: $x_1\le x_2\le \dots\le x_m$, where $x_i$ is the number of votes that the person $p_i$ receives.
If
$$
\sum_{i=1}^{\lceil\frac m2 \rceil}x_i >r,
$$
then there cannot be $\lceil\frac m2 \rceil$ honest man in $M$. Note that $\lceil\frac m2 \rceil=m/2$ if $m$ is even and $\lceil\frac m2 \rceil=(m+1)/2$ if $m$ is odd.
In this case the first alternative is true:  there are more enemies than honest people in the set $M$, and the dictator is able to know it.

Else
$$
\sum_{i=1}^{\lceil\frac m2 \rceil}x_i \le r,
$$
and then the complementary set $M_1=\{p_i\ |\ i> \lceil\frac m2 \rceil\}$ has $\lfloor\frac m2 \rfloor$ elements and receives at least $n-r$ votes (and at most $r$ fake votes).
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P2:}$
Set $F_0:=F$. Then $F_0$ receives $N$ votes, from which $N/10$ are fake votes.

Hence, by P1, either $F_0$ has more enemies than honest man and the dictator knows it, or there is a subset $F_1$ with $f_1:=\lfloor \frac f2 \rfloor$ elements, which receives at least $N-N/10=9N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_1$ has more enemies than honest man and the dictator knows it, or there is a subset $F_2$ with $f_2:=\lfloor \frac {f_1}2 \rfloor$ elements, which receives at least $9N/10-N/10=8N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_2$ has more enemies than honest man and the dictator knows it, or there is a subset $F_3$ with $f_3:=\lfloor \frac {f_2}2 \rfloor$ elements, which receives at least $8N/10-N/10=7N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_3$ has more enemies than honest man and the dictator knows it, or there is a subset $F_4$ with $f_4:=\lfloor \frac {f_3}2 \rfloor$ elements, which receives at least $7N/10-N/10=6N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_4$ has more enemies than honest man and the dictator knows it, or there is a subset $F_5$ with $f_5:=\lfloor \frac {f_4}2 \rfloor$ elements, which receives at least $6N/10-N/10=5N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_5$ has more enemies than honest man and the dictator knows it, or there is a subset $F_6$ with $f_6:=\lfloor \frac {f_5}2 \rfloor$ elements, which receives at least $5N/10-N/10=4N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_6$ has more enemies than honest man and the dictator knows it, or there is a subset $F_7$ with $f_7:=\lfloor \frac {f_6}2 \rfloor$ elements, which receives at least $4N/10-N/10=3N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_7$ has more enemies than honest man and the dictator knows it, or there is a subset $F_8$ with $f_8:=\lfloor \frac {f_7}2 \rfloor$ elements, which receives at least $3N/10-N/10=2N/10$ votes.

But $f_8\le f/2^8\le N/2560$ and $F_8$ receives $2N/10$ votes, so each person in $F_8$ receives on average $\frac{N/5}{N/2560}=512$ votes, which is impossible (HERE WE USE THE "KNOWS AT MOST 500 PEOPLE" ASSUMPTION). So, for some
$i=0,\dots,7$, the set $F_i$ has more enemies than honest people and the dictator is able know it.
$$\tag*{$\Box$}$$
${\bf Proof\ of\ P3:}$

Assume that your country has $N=2560n$ people for some positive integer $n$. The distribution is the following:

128n people receive exactly one vote,

64n people receive exactly 2 votes,

32n people receive exactly 4 votes,

16n people receive exactly 8 votes,

8n people receive exactly 16 votes,

4n people receive exactly 32 votes,

2n people receive exactly 64 votes,

n people receive exactly 128 votes,

and n people receive exactly 256 votes.

It is left to the reader to prove that for every set $A\subset X$ there is a subset $B$ of $A$ with $\# B\ge \# A/2 $ such that all people in $B$ have together at most 256n votes. These votes could be all fake votes, so there is no way to determine with 100% certainty a subset with more enemies than honest man.
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P4:}$

Consider the oriented graph, where the people are the vertices and the votes are the oriented edges.

We construct $G$ inductively:

First we take $G$ to be the set of vertices of cycles. Then take the largest path that is not in $G$ (all paths eventually end in a cycle).
If the path has an even number of vertices not in $G$, include all the vertices in $G$. If it has an odd number of vertices not in $G$,
then include all but the first vertex in $G$.

Clearly in each oriented path with an even number of vertices, there are at least the same number of enemies than honest people.
So, by construction, $G$ has at least the same number of enemies than honest man. Moreover, any voted man has a path that leads to a cycle (and he is not the first vertex of that path), so eventually he will be included in $G$. Hence $F\subset G$, as desired.
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P5:}$
Finally we prove P5. We can assume that the number of people in $G$ is even: if there is an odd cycle this renders a set with more enemies than honest people and at each inductive step we add an even number of people to $G$.

So let $\#G=2p\le N/5$. Then $G_0:=G$ receives $N-2p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes. Clearly P1 still holds if we consider only votes in $X\setminus G$,
 so either $G_0$ has more enemies than honest man and the dictator knows it, or there is a subset $G_1$ with $g_1:=p$ elements, which receives at least
$N-2p-(N/10-p)=9N/10-p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

Again by P1, either $G_1$ has more enemies than honest man and the dictator knows it, or there is a subset $G_2$ with $g_2:=\lfloor\frac p2\rfloor$ elements, which receives at least
$9N/10-p-(N/10-p)=8N/10$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_2$ has more enemies than honest man and the dictator knows it, or there is a subset $G_3$ with $g_3:=\lfloor\frac {g_2}2\rfloor$ elements, which receives at least
$8N/10-(N/10-p)=7N/10+p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_3$ has more enemies than honest man and the dictator knows it, or there is a subset $G_4$ with $g_4:=\lfloor\frac {g_3}2\rfloor$ elements, which receives at least
$7N/10+p-(N/10-p)=6N/10+2p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_4$ has more enemies than honest man and the dictator knows it, or there is a subset $G_5$ with $g_5:=\lfloor\frac {g_4}2\rfloor$ elements, which receives at least
$6N/10+2p-(N/10-p)=5N/10+3p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_5$ has more enemies than honest man and the dictator knows it, or there is a subset $G_6$ with $g_6:=\lfloor\frac {g_5}2\rfloor$ elements, which receives at least
$5N/10+3p-(N/10-p)=4N/10+4p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_6$ has more enemies than honest man and the dictator knows it, or there is a subset $G_7$ with $g_7:=\lfloor\frac {g_6}2\rfloor$ elements, which receives at least
$4N/10+4p-(N/10-p)=3N/10+5p$ votes (from $X\setminus G$).

But $g_7\le p/2^6$ and $G_7$ receives $3N/10+5p$ votes, so each person in $G_7$ receives on average at least $\frac{3N/10+5p}{p/2^6}=\frac{192}{10}\frac {N}{p}+320\ge 512$ votes, since $\frac{N}{p}\ge 10$. This is
impossible (HERE WE USE THE "KNOWS AT MOST 500 PEOPLE" ASSUMPTION), so for some
$i=0,\dots,6$ the set $G_i$ has more enemies than honest people and the dictator is able to know it.
$$\tag*{$\Box$}$$

${\bf FINAL\ NOTES:}$

The proof of P5 is valid even if the bound of the number each person knows is increased from 500 to 4096; in that case people in $G_{10}$ would have on average 4096 votes.

If the bound is 250 instead of 500, or if only 9% (or less) of the people are enemies, then the distribution of votes is sufficient to determine the required set.

If $N$ is small, then at some moment $g_i=1$, and it will be necessarily an enemy.

In order to avoid the trivial solution "The dictator is honest and so he knows an enemy" we should require that the condition is true for all people but the dictator. This would be consistent with changing the dictator for some computer (which is also useful in order to process all the denouncing data).

Allowing the dictator to be an enemy would turn the situation less realistic.

I've made an assumption, that the number of people $N$ is way much higher than $500$.

Then I've considered the worst case, where every man knows $500$ other people.

In this case honest man have probability of not being shown as an enemy averagely $$p_h=1^{450}.998^{50}\approx .9047$$

Analogical probability for enemies is averagely $$p_h=.98^{450}.998^{50}\approx .0001$$

Thus we can compute the probabilities of being picked:
$$P_h=1-p_h\approx .0953 \\ P_e = 1-p_e\approx .9999$$

Now if we put all picked people to the jail, there will be $$K_e=P_e\cdot.1\cdot N\approx.09999\cdot N$$ enemies and $$K_h=P_h\cdot.9\cdot N\approx.08573 \cdot N$$ honest people.

Thus there are more enemies than honest people in jail.

Edit

I also want to refer to your 'non-cycle' strategies (to long for a comment):

Consider case, where:

30 enemies voted for one honest man and this man voted against one of this enemies
in 26 groups 19 honest men voted against one enemy
in one group 18 honest men voted against one enemy
all enemies from these 27 groups voted against one man from one of these groups.

So we have then:

Population of 570 people with 57 enemies and 30 voted men
2 honest men voted by 30 and 27 votes
26 enemies voted by 19 men each
1 enemy voted by 18 men
1 enemy voted by 1 man

Picking 10% with the highest ammount of votes will cause picking 2 honest men and 1 enemy - there are no more enemies than honest people in this group

Picking the smallest group with at least 10% may be problematic - this approach cause selection of 2 honest men and no enemy.