text:
# Why perceptron does not converge on data not linearly separable

This is how I understand the perceptron algorithm.

The perceptron loss function is the hinge loss $$\ell(w,x,y) = \max(0, -yw\cdot x)$$. Suppose the data set is $$D = \{(x_1,y_1),\dots,(x_n,y_n)\}$$ with $$y_i \in \{-1,1\}$$. The perceptron criterion is $$E(w) = \sum_i \ell(w, x_i, y_i) = \sum_i \max(0, -y_iw\cdot x).$$ The perceptron algorithm tries to minimize $$E(w)$$ using gradient descent. The gradient of $$E(w)$$ with respect to $$w$$ is $$\nabla E(w) = \sum_i \left\{ \begin{array}{ll} \mathbf{0} & \text{ if } \ell(w,x_i,y_i) = 0\\ -y_ix_i & \text{ otherwise } \end{array}\right..$$ So the perceptron updates the $$w$$ according to $$w^{(t+1)} = w^{(t)} - \eta \nabla E(w^{(t)}) = w^{(t)} + \eta \sum_{i\in M(t)} y_ix_i$$ where $$M(t)$$ is the set of points misclassified by $$w^{(t)}$$. Since we can define another equivalent sequence of weight vectors $$v^{(t)} = (1/\eta)w^{(t)}$$, we can just take $$\eta = 1$$.

I know that $$w^{(t)}$$ will converge to a seperating hyperplane if one exists and $$E(w)$$ will converge to $$0$$.

My question is about when the data set is not linearly separable. In that case, does $$E(w)$$ converge to some minimum?

If $$E(w)$$ attains some minimum, its gradient there has to be $$\mathbf{0}$$. One possibility is that all the terms in the sum of $$\nabla E$$ are 0, which means that the dataset is linearly seperable and this is contradiction. The other possibility is that the sum of $$-y_ix_i$$ over the misclassified points is somehow $$\mathbf{0}$$.

The behavior appears to actually depend on the learning rate $$\eta$$; a smaller $$\eta$$ affects which points are misclassified in the next iteration, which affects the weight update more than just by the simple scaling you alluded to.
Let $$\{(x_j, y_j)\}_{j\in J}$$ be the set of points misclassified by $$w$$ (the ones with non-zero terms in the sum of $$\nabla E$$). Under the hypothesis that $$-\sum_{j\in J} y_j x_j = 0$$,
$$\sum_{j\in J} y_j w \cdot x_j = w \cdot \left(\sum_{j\in J} y_j x_j\right) = 0,$$


text:
# Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$

Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$

Here is the proof

Without loss of generality , I assume that $m > n$ then we know that $$F_m = 2 + F_0F_1F_2........F_nF_{n+1}.....F_{m-1}$$ I assumed here that $n > 2$ and $n < m-1$

Now we assume that $\gcd(F_n,F_m) = d$ then $d \mid F_n$ and $d \mid F_m$

Now if $d \mid F_n$ then $d \mid F_0F_1.....F_nF_{n+1}...F_{m-1}$ and so $d$ divides any linear combination of $F_m$ and $F_0F_1.....F_nF_{n+1}...F_{m-1}$, In particular $d \mid Fm- F_0F_1.....F_nF_{n+1}...F_{m-1}=2$ and hence $$d \mid 2$$

Now since all Fermat numbers are odd then $d \neq 2$ and hence $d=1$

Now I want to use this to prove that there exists infinitely many primes.

I know that since Fermat numbers form an infinite sequence of increasing numbers and each Fermat number is relatively prime to all other Fermat numbers then we have infinitely distinct prime divisors for each composite Fermat numbers and we also add to those Fermat prime numbers.

I feel like there is a better mathematical argument that that novel that I wrote above :)

• What is the question? The proof is OK. – Winther Apr 23 '15 at 8:16
• Is there a more concrete way to prove that there are infinitely many primes ? using Fermats numbers – alkabary Apr 23 '15 at 8:18
• The proof that Fermat numbers are pairwise coprime looks fine. In particular, if you take $p_n = \mbox{minimum prime dividing } F_n$, then $\{ p_n \}_n$ is an infinite set of primes. – Crostul Apr 23 '15 at 8:19
• You can make the argument more compact and elegant if you want, but you basically need all the ingredients that is in there now. For the same proof see for example this – Winther Apr 23 '15 at 8:20
• A proof "from the book" is given in Aigner, Ziegler. – Dietrich Burde Apr 23 '15 at 8:59

I think your proof is essentially fine.

I'm not sure if you need to prove $F_n = 2+F_0F_1F_2\ldots F_{n-1}$, but I'll add that by induction. Base case: $F_0=3 \\ F_1 = 5 = 2+F_0$

Inductive step: Assume that the stated relation holds for $F_k$, so $F_k-2 = F_0F_1F_2\ldots F_{k-1}$. Then note that

\begin{align} (F_k)(F_k-2) &= (2^{2^k}+1)(2^{2^k}-1) \\ &= (2^{2^k})^2-1\\ &= 2^{2^{k+1}}-1\\ &= F_{k+1}-2\\ \end{align}

And so $F_{k+1} = 2+F_k(F_k-2) = 2+ F_0F_1F_2\ldots F_{k-1}F_k$ as required to complete the induction.

To show that for $m>n\ge 0, \gcd(F_m,F_n)=1$, your proof can be shortened, but doesn't change in essence:

\begin{align} F_m &= 2+F_0F_1F_2\ldots F_{m-1} \\ &=2+kF_n\\ \end{align}

Then for $d=\gcd(F_m,F_n)$ we have $d \mid F_m$ and $d \mid kF_n$, so also $d \mid 2$. We know that $F_m$ is odd $\Rightarrow d \ne 2$, giving $d=1$.

The infinite sequence of Fermat numbers therefore does not share any prime factors between terms, meaning there are an infinite number of primes.

format: plain


text:
# Getting around the effects of low Mars gravity

If my Mars colonists don't want to be crippled, they need to bear their own weight as close to Earth normal as possible for their waking hours. How about shoes (leather from goats and sheep) with magnetic bits engineered inside the soles. Then, for the other part of the equation, what about hard or soft flooring that contains iron or steel particles. If that won't work, what about belt, shoes, or other clothing containing weighted fabric or inserts? Now, how about the babies who can’t walk and may never do so if their bones aren’t strengthened in some manner? What about the food animals? Can they put shoes on the animals' (sheep, goats, etc.) hooves such as horses wear? What do we do about fowl? Can a magnetic device be attached the the bottom of their feet? I can’t think how artificial gravity could work on a planet’s surface. No convenient alien technology here, just orphaned settlers.

• What issues are you aware of with low gravity? There's quite a lot of issues that are associated with low gravity, not all of which are helped by such shoes. Understanding which of those issues you perceive as important may help direct our answers. – Cort Ammon Sep 21 '16 at 4:00
• Russian astronauts have survived +500 days in absolutely no gravity, and they wer not "crippled". Their possibilities for exercise on MIR were rather limited, compared to ISS or spending the day as farmer and construction worker on Mars. – Karl Sep 22 '16 at 3:13
• The Defense Dept would consider 500 days a TDY (temporary duty assignment). These colonists would be conceived, born, and live their entire lives in 1/3 Earth normal gravity. "Bone remodels in response to stress in order to maintain constant strain energy per bone mass throughout. To do this, it grows denser in areas experiencing high stress, while resorbing density in areas experiencing low stress. On Mars, where gravity is about one-third that of earth, the gravitational forces acting on astronauts' bodies would be much lower, causing bones to decrease in mass and density.: (Wikipedia). – Phyllis Stewart Sep 22 '16 at 18:31

The first generation born on mars could be genetically manipulated to be better fit for the enviroment. Similar solution can work for animals. In fact we don't know much about how low gravity will affect pregnancy.

Aside from that, I agree with Andreas Heese's answer.

As per the effects that low gravity has, this flow chart by the NSBRI (National Space Biomedical Research Institute) should serve as guideline:

You may also want to see how Men and Women Adapt Differently to Spaceflight:

Of course Mars has other challeges such as the lack of magnetic field, the ambient temperature, and the isolation and psicological stress of the settlers.

• Mars is not microgravity. – Karl Sep 22 '16 at 2:08
• @Karl yeah, you are right. Mars gravitational accelarion is 0.378g, what's that, decigravity? As long as we don't have information on the effects of prolonged decigravity on humans - microgravity should serve as guideline. – Theraot Sep 22 '16 at 2:51
• It's a bit less than half of earths gravity. Why would there be any problems? – Karl Sep 22 '16 at 3:06
• @Karl for same reason they are in micro gravity, we are not used to be in different gravity, and our systems heavily exploit gravity presence, in way which will wonder you. For the moment no one knows will there be or will it not to be a problems with mars gravity. Do you never wondered yourself, how how for god shake 1 cell is able to convert to adult mammal? We talking about very complex biological machine, and our current knowledge do not allow us to predict results, so preparing to worst case scenario is pretty wise if there will be problem, if not, fine, better for us. – MolbOrg Sep 22 '16 at 14:12
• Flying animals adapt best to low gravity (1/3 Earth normal). Fish will swim in circles unless a light source is provided to give them proper orientation for "up and down." The fetus must orient head down before birth. Don't you think that is a matter of gravity assistance? If land and water animals have trouble, of course human fetuses will as well. Wikipedia: Bone remodels in response to stress in order to maintain constant strain energy per bone mass throughout. To do this, it grows denser in areas experiencing high stress, while resorbing density in areas experiencing low stress. – Phyllis Stewart Sep 22 '16 at 18:45

I am assuming you did some research and found out that under orbital gravity (ISS), bones lose density. I also assume that this is fully true, understood well, and also applies for low gravity of mars. I am not sure about that, or if it even is a problem at all, but i don't want to research or discuss that, as it is out of focus for the question.

Putting on heavy shoes does not increase your bone stability. It doesn't even increase the "weight" of your body, it's just dead weight... on your shoes. While it becomes harder to walk, it will strengthen your muscles, but to increase bone density, you need weight to REST on the bones. So you'd need to shoulder huge weights, so they'd push down on your body. Wearing super heavy clothing might help (and it might look cool having everyone walk around in platemail).

But i think the basic problem of bones requiring stress to fully develop couldn't be handled this way. These days in space, bone density problems are countered by intensive special training. Maybe you can have facilities where adults can train hard to keep their bodies healthy? I have no idea how to solve the problem for animals or infants, though. Maybe a special diet or medicine could solve the problem for you?

• +1 for martians wearing full platemail. It also makes sense with their intensive training in... martian arts. There is definitely not enough media about martian knighnjas™ – xDaizu Sep 21 '16 at 12:02
• What about the fetuses, infants, and children. They are most at risk. I am not proposing heavy shoes. The idea is to create a higher magnetic pull by incorporating pairs of attracting elements in the footwear and the flooring. Gravity creates the needed stressors for bone formation and maintenance. A properly calculated magnetic pull could, I believe, create the same effect. Otherwise, unless the problem is solved, long term colonization on planets with gravity less than 90% Earth normal will never be possible. – Phyllis Stewart Sep 22 '16 at 18:36
• Your idea of special facilities and periods of intense training made me think of the low-tech solution of merry-go-rounds all over the place. Those spinning (everyone takes turns) are working their muscles and getting exercise, those riding get the extra "weight" (acting like gravity to stress the bones) - especially if the merry-go-rounds are constructed with walls or a deeply sloped floor, so people walk inside and more of that force can run head-to-feet not just sideways. Kids and even infants should be able to play inside, walk or crawl for extra gravity-like stress while developing. – Megha Sep 23 '16 at 1:26

Who says there are any significant health problems under mars gravity? We know that most effects of absolutely no gravity can be fought well with one hour of physical exercise (as can a lot of earth health problems, btw. ;-)), and Mars still has $0.4 g$. I think any planet able to hold an atmosphere at civilised temperatures is totally unproblematic with respect to gravity.

The main problem esp. early Russian cosmonauts experienced is loss of bone density and weakening muscles, like what is known on earth from people with e.g complicated bone fractures, requiring extremities to be immobilised for an extended period of time.

Bone (& muscle) tissue does not grow in response to gravity, but to the forces the muscles exert on them. The problem in zero g is that practically nothing does require any force at all. So you put an hour of exercise on the schedule of astronauts, and it helps a lot. As does very careful exercising for recuperating patients. They are not 100% fit when they return to earth, or to normal life, but far from having turned in wracks. The earliest Russian long-term cosmonauts had to be carried on stretchers after return. When the space shuttle brought back long term crew members from ISS, they walked down the gangway on their own.

A person that lounges about all day and watch TV turns sick, on Mars probably faster than on earth. Luckily there is no TV there, at least in the beginning. But work on Mars would still be work, especially outside in your (rather heavy and rigid) pressure suit. Ten kg rucksack feels like 4 kg only? Have one twice as large!

I wouldn't bet that raising children on Mars would be as uncritical. I certainly would not do it on a space station without a lot of animal experiments before. Maybe have a centrifugal kindergarten. ;-)

But the basic message would be the same: It's not gravity, it is your musclework that keeps the bones healthy.

• they show you only that, because what else to show)) Which chemicals they are using, they will never tell you. I bet doping sportsmen's are working for space program)) most likely indirectly) – MolbOrg Sep 22 '16 at 14:19
• Persons living their entire lives on a planet with .3 Earth normal gravity and who weigh only half what they would on Earth will have significant bone formation challenges. Physical exercise must be weight bearing and be calibrated to replicate Earth's normal effects. Infants, children, and the elderly will be unable to participate. No chemicals can mimic gravity's effects. A process or application to produce the effects of artificial gravity must be developed to enable long term space colonization. – Phyllis Stewart Sep 22 '16 at 18:53
• u might find it interesting to read link , link , link This one is funny: selecting candidates for testing take look at exclusion criteria, there are obvious reasons, but still. – MolbOrg Sep 22 '16 at 21:41

Same as we do in space, I should think. Use weight training and anchored treadmills to retain as much muscle tone as possible in an effort to stave off osteoporosis. I don't see that having heavy shoes will do anything other than tone up the leg muscles.

Andreas answered as I typed the above, and he's right.

For children, you just have to do the best that you can. Over the course of many generations, they would ideally start to evolve and adapt to the new gravity, but the chances are that your colony will die out before then - to my mind, it'll be doubtful that enough children will survive to procreate more than another generation or two unless you were really strict on the weight training.

Obviously, the more time taken up in physical exercise/conditioning, the less time can be used for more productive (survival orientated) tasks. Chances are that the exercise will come second place.

I don't think you'd have large animals - chickens would probably be the best source of food and you could keep those in small/low coops to prevent them from harming themselves. Horses/goats/cows don't really have a place on Mars - if there were there, then they'd be an immediate food source.

• If the problem is solved for humans, it would be solved for all animals as well. Sheep, goats, pigs, fowl, fish, and rabbits could all be good protein sources. Cows are obviously far too inefficient for use. A wide variety of foods must be provided for health and emotional well-being. Remember, this is generations or persons living all their lives on Mars. I'm afraid genetic manipulation would be of doubtful effect. This is a purely physical question. – Phyllis Stewart Sep 22 '16 at 18:58

Large Jumps? A person of normal bodily strength on mars should be able to jump a lot higher than on earth, lift heavier things, leap further. If you design the base without stairs or use some other design that forces them to do these things regularly then your people could maintain normal fitness by leaping around and hanging to the ceiling. Alternatively you can make a parabolic floor and rotate it so that real and centrifugal gravity combine.

• Great idea! Lets give them centrifugal beds! xkcd.com/123 – Karl Sep 22 '16 at 11:30
• The bones do not need aerobic exercise. They need weight-bearing activity. Besides, you can't teach toddlers to perform large jumps. Vitamin and mineral supplements won't have any effect. Weight-bearing only. In addition, the colonists will weigh only half what they would on Earth. This significantly compounds the issue. – Phyllis Stewart Sep 22 '16 at 18:49

One important question is, will they ever return to earth? 0.4g is not 0g and I bet body will adapt to this environment with muscle and bone loss, but not too much to be crippled.

End result? If they are to return Earth, they will not be able to walk unassisted. But on Mars they would probably be even healthier.


text:
Small Universal Point Sets for k-Outerplanar Graphs

Small Universal Point Sets for k-Outerplanar Graphs A point set $$\mathcal{S} \subseteq \mathbb {R}^2$$ S ⊆ R 2 is universal for a class $$\mathcal G$$ G of planar graphs if every graph of $$\mathcal{G}$$ G has a planar straight-line embedding on $$\mathcal{S}$$ S . It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a subquadratic universal point set still remains one of the most fascinating open problems in Graph Drawing. In this paper we make a major step towards a solution for this problem. Motivated by the fact that each point set of size n in general position is universal for the class of n-vertex outerplanar graphs, we concentrate our attention on k-outerplanar graphs. We prove that they admit an $$O(n \log n)$$ O ( n log n ) -size universal point set in two distinct cases, namely when $$k=2$$ k = 2 (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Discrete & Computational Geometry Springer Journals

Small Universal Point Sets for k-Outerplanar Graphs

41 pages

/lp/springer_journal/small-universal-point-sets-for-k-outerplanar-graphs-7TfDLhueYa
Publisher
Springer Journals
Copyright © 2018 by Springer Science+Business Media, LLC, part of Springer Nature
Subject
Mathematics; Combinatorics; Computational Mathematics and Numerical Analysis
ISSN
0179-5376
eISSN
1432-0444
D.O.I.
10.1007/s00454-018-0009-x
Publisher site
See Article on Publisher Site

Abstract

A point set $$\mathcal{S} \subseteq \mathbb {R}^2$$ S ⊆ R 2 is universal for a class $$\mathcal G$$ G of planar graphs if every graph of $$\mathcal{G}$$ G has a planar straight-line embedding on $$\mathcal{S}$$ S . It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a subquadratic universal point set still remains one of the most fascinating open problems in Graph Drawing. In this paper we make a major step towards a solution for this problem. Motivated by the fact that each point set of size n in general position is universal for the class of n-vertex outerplanar graphs, we concentrate our attention on k-outerplanar graphs. We prove that they admit an $$O(n \log n)$$ O ( n log n ) -size universal point set in two distinct cases, namely when $$k=2$$ k = 2 (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs).

Journal

Discrete & Computational GeometrySpringer Journals

Published: May 29, 2018

You’re reading a free preview. Subscribe to read the entire article.

DeepDyve is your personal research library

It’s your single place to instantly
discover and read the research
that matters to you.

over 18 million articles from more than
15,000 peer-reviewed journals.

All for just $49/month Explore the DeepDyve Library Search Query the DeepDyve database, plus search all of PubMed and Google Scholar seamlessly Organize Save any article or search result from DeepDyve, PubMed, and Google Scholar... all in one place. Access Get unlimited, online access to over 18 million full-text articles from more than 15,000 scientific journals. Your journals are on DeepDyve Read from thousands of the leading scholarly journals from SpringerNature, Elsevier, Wiley-Blackwell, Oxford University Press and more. All the latest content is available, no embargo periods. DeepDyve Freelancer DeepDyve Pro Price FREE$49/month
\$360/year

Save searches from
PubMed

Create lists to

Export lists, citations


text:
# Evaluate inverse trig functions without calculator

How to find the inverse of: $$\cos(c)=\frac{1}{3}$$ In other words, i'm trying to solve for c and without a calculator. If it's hard or not possible, then how would you go about solving inverses in. Evaluating Inverse Trigonometric Functions Without Using the Calculator Use the properties of inverse trigonometric functions to evaluate the expression Find the exact value of the composite trigonometric function Write an algebraic expression that is equivalent to the expression Evaluating Inverse Trigonometric Functions Without Using the. Graphs for inverse trigonometric functions. Calculate Arcsine, Arccosine, Arctangent, Arccotangent, Arcsecant and Arccosecant for values of x and get answers in degrees, ratians and pi. Graphs for inverse trigonometric functions. This calculator will find the inverse trigonometric values for principal values in the ranges listed in the table.

# Evaluate inverse trig functions without calculator

[The easiest way to work with inverse trig functions is to have a chart handy with values rather quickly and efficiently — without resorting to chart or calculator. (1) Know that cos, sec functions are restricted to quad 1 and 2; (2) Know that tan, cot, sin, csc are restricted to quad 1 and 4; (3) And when you. The easiest way to work with inverse trig functions is to have a chart handy with the exact values of the functions. When you work with trigonometry a lot, you. The inverse trigonometric functions. We already Inverse trig functions do the opposite of the “regular” trig functions. .. ∘Evaluate with a calculator.. Sal introduces arcsine, which is the inverse function of sine, and discusses its principal range. You could use the Maclauren series for arcsin: arcsinx=x+x36+3x+5x+⋯ . So arcsin≈ This is in radians, so convert to. Evaluating Inverse Trigonometric Functions Without Using the Calculator. Overview · Evaluate Inverse Sine · Evaluate Inverse Cosine · Evaluate Inverse Tangent. | Mar 13,  · Trigonometry involves calculating angles and functions of angles, such as the sine, cosine and tangent. Calculators can be handy in finding these functions because they have sin, cos and tan buttons. However, sometimes you won't be allowed to use a calculator on a homework or exam problem or you might simply not. The easiest way to work with inverse trig functions is to have a chart handy with the exact values of the functions. When angles other than the most common or popular are involved, you can either use a table or get out your handy-dandy scientific calculator. When you work with trigonometry a lot, you soon [ ]. How to find the inverse of: $$\cos(c)=\frac{1}{3}$$ In other words, i'm trying to solve for c and without a calculator. If it's hard or not possible, then how would you go about solving inverses in. Evaluating Inverse Trigonometric Functions Without Using the Calculator Use the properties of inverse trigonometric functions to evaluate the expression Find the exact value of the composite trigonometric function Write an algebraic expression that is equivalent to the expression Evaluating Inverse Trigonometric Functions Without Using the. Graphs for inverse trigonometric functions. Calculate Arcsine, Arccosine, Arctangent, Arccotangent, Arcsecant and Arccosecant for values of x and get answers in degrees, ratians and pi. Graphs for inverse trigonometric functions. This calculator will find the inverse trigonometric values for principal values in the ranges listed in the table. Precalculus Worksheet Name _____ Section – Inverse Trig Functions Period _____ Evaluate the given expression without the aid of a calculator. 1. sin 1 1 2 §· ¨¸ ©¹. Feb 26,  · If you ever want to become decent at trigonometry, you have to understand the connection between right triangles and the unit circle shown here. You can see the radii drawn at various angles (measured in radians and degrees) all the way around t.] Evaluate inverse trig functions without calculator The easiest way to work with inverse trig functions is to have a chart handy with the exact values of the functions. When angles other than the most common or popular are involved, you can either use a table or get out your handy-dandy scientific calculator. When you work with trigonometry a lot. Calculate Arcsine, Arccosine, Arctangent, Arccotangent, Arcsecant and Arccosecant for values of x and get answers in degrees, ratians and pi. Graphs for inverse trigonometric functions. Often when you are asked to calculate the trig function of an angle without a calculator, you will be given a right triangle, and the angle you are asked about is one of the angles in the triangle. Evaluating Inverse Trigonometric Functions Without Using the Calculator Use the properties of inverse trigonometric functions to evaluate the expression. Precalculus Worksheet Name _____ Section – Inverse Trig Functions Period _____ Evaluate the given expression without the aid of a calculator. How do I find angles using inverse trig functions without a calculator? How can I evaluate trigonometry with a four-function calculator? Bhava Nath Dahal, Breaking Classical Rules in Trigonometry- 5 new methods & higher-degree equation. Sal introduces arctangent, which is the inverse function of tangent, and discusses its principal range. If you're seeing this message, it means we're having trouble. Free trigonometric equation calculator - solve trigonometric equations step-by-step. Given a sine, cosine, or tangent value, find the principle angle who has this value. In other words, find the arcsine, arccosine, or arctangent of that value. Free functions inverse calculator - find functions inverse step-by-step. Identities Proving Identities Trig Equations Trig Inequalities Evaluate Functions Simplify. The calculator will find the inverse of the given function, with steps shown. If the function is one-to-one, there will be a unique inverse. Trig Function Evaluation. One of the problems with most trig classes is that they tend to concentrate on right triangle trig and do everything in terms of degrees. Then you get to a calculus course where almost everything is done in radians and the unit circle is a very useful tool. INVERSE TRIGONOMETRIC FUNCTIONS. The range of y = arcsin x. The range of y = arctan x. The range of y = arccos x. The range of y = arcsec x. sin −1 x. The inverse sine. The inverse relations. T HE ANGLES in theoretical work will be in radian measure. Thus if we are given a radian angle, for example, then we can evaluate a function of it. So, be careful with the notation for inverse trig functions! There are, of course, similar inverse functions for the remaining three trig functions, but these are the main three that you’ll see in a calculus class so I’m going to concentrate on them. To evaluate inverse trig functions remember that the following statements are equivalent. Evaluate trig functions without the use of a calculator Name_____ ID: 1 ©n T2W0g1y6H aKAuVt^aJ dSUoTfnthwuaVrxei QLyLWCS.N m DAul[lX PrMiegnhetKsY ZrRessbe\rcvuerdp. Find the exact value of each trigonometric function. 1) sec ° 2) sin - p 4 3) cos 4p 3 4) tan 45° 5) csc ° 6) cos - 3p 4 7) sec ° 8) cot 4p 3. How do you evaluate #arccos(0)# without a calculator? Trigonometry Inverse Trigonometric Functions Basic Inverse How do you use inverse trig functions to find. Oh yeah, the ranges of the inverse trig functions, because that's what your calculator is using when it displays an answer; you should be aware that the answer The Machine gives you may be in the wrong quadrant for your application, so from there, you need to know how to adapt the displayed angle to the correct angle for your problem, as.

## EVALUATE INVERSE TRIG FUNCTIONS WITHOUT CALCULATOR

Evaluate inverse trig functions without a calculator
The voynich code antithesis adobe, rei arthur anime ing, gta san andreas 300 mb er, african music instrumentals r&b, aytac dogan deva rar, flappy bird apk tablet

## 2 thoughts on “Evaluate inverse trig functions without calculator”

1. Nikozshura says:

works fine ???? in win 8.1 64 bit ?

2. Malajinn says:

many thank's !!!


text:
# Math Help - rotational symmetry

1. ## rotational symmetry

The diagram below has rotational symmetry. How many regular pentagons are there?.

2. I see at least 7. 1 Outer pentagon. 1 inner central pentagon. 5 small pentagons forming the central pentagon. There may be more, but I doubt it.

3. 5 small pentagons forming the central pentagon.
I don't see those. The central pentagon is formed with quadrilaterals, isn't it? If the question is about rotational symmetry, then perhaps we're supposed to get five pentagons from each of the inner and outer ones by rotations through 360/5 degrees? I don't know, I'm just askin'. If this is true, you'd have 10 pentagons, right? I'm assuming we're not allowed reflections.

4. Oops, you are right. I was blind.


text:
# The Polynomial Method In Quantum and Classical Computing Scott Aaronson (MIT) OPEN PROBLEM.

## Presentation on theme: "The Polynomial Method In Quantum and Classical Computing Scott Aaronson (MIT) OPEN PROBLEM."— Presentation transcript:

The Polynomial Method In Quantum and Classical Computing Scott Aaronson (MIT) OPEN PROBLEM

Overview The polynomial method: Just an awesome tool that every CS theorist should know about Goes back to the prehistory of the field (1960s), but also plays a major role in current work [including at this FOCS] on machine learning, quantum computing, circuit lower bounds, communication complexity… Idea: Reduce CS questions to questions about the minimum degree of real polynomials Easy to learn! Look ma, no quantum

This Talk: Just Some Basics 1. Polynomials in machine learning - Perceptrons 2. Polynomials in quantum computing - Optimality of Deutsch-Jozsa and Grover algorithms - Collision lower bound 3. Polynomials in circuit complexity - Linial-Mansour-Nisan and Bazzi 4. Polynomials everywhere! - Communication complexity, oracles, streaming… Stuff I wish I could cover but cant for lack of time - Polynomials over finite fields (Razborov-Smolensky) - Reduction of communication problems to polynomials - Sherstovs pattern matrix method - Deep connections to Fourier analysis

Our story starts in St. Petersburg, around 1889… Dmitri Mendeleev (periodic table dude) A. A. Markov (inequality dude) привет! I proved a cool theorem: if p is a quadratic, And what if p has degree d? Uhh … youre on your own

Markov did generalize Mendeleevs bound to arbitrary degree (about which more later) He thereby helped start a field called approximation theory Approximation theory is a proto-complexity theory! Real polynomials = Model of computation Degree = Complexity measure So, maybe not so surprising that it ends up being related to actual complexity theory…

1. POLYNOMIALS IN MACHINE LEARNING

Fast-forward to 1969… Bill Ayers was working for the McCain08 campaign And AI researchers were studying perceptrons A perceptron of order k is a Boolean function f:{0,1} n {0,1} thats a threshold of subfunctions on at most k variables each f1f1 fmfm f2f2 … f

Minsky and Papert: Small perceptrons have serious limitations! Suppose f:{0,1} n {0,1} is represented by an order-k perceptron Then theres clearly a degree-k polynomial p:R n R such that for all x 1,…,x n {0,1}, Furthermore, without loss of generality p is multilinear: no variable raised to higher power than 1 Application: killed neural net research for a decade

Example: The PARITY function Suppose for all x 1,…,x n {0,1}. Then what can we say about deg(p)? Key idea: Symmetrization Replace multivariate polynomials by univariate ones, which are easier to understand Theorem: deg(p) n

Let Key Lemma: q(k) is itself a polynomial in k, of degree at most d How Symmetrization Works Let

Proof: By linearity of expectation, which is a degree-|S| polynomial in k.

So, suppose theres an order-k perceptron computing the parity of n bits Then theres a degree-k multilinear polynomial p such that Hence theres a degree-k univariate polynomial q such that for all k=0,…,n, Must have degree n

2. POLYNOMIALS IN QUANTUM COMPUTING

Quantum Query Model In One Slide Apply a unitary transformation What are the allowed operations? Initialize vector of amplitudes Measure Outcome i observed with probability | i | 2 Query the input bits Quantum state: Unit vector in C n One further detail: The quantum state can have more than n dimensions, with multiple components querying each x i, as well as components that dont make queries at all Complexity Measure: Q(f) = minimum number of queries needed to compute a Boolean function f with probability 2/3, on all inputs x=x 1 …x n

Example: The Deutsch-Jozsa Algorithm Does something spectacular: Computes the XOR of two bits with one oracle call! By computing x 1 x 2, x 3 x 4, etc., can compute the parity of n bits with n/2 oracle calls Is that optimal?

Lemma (Beals et al. 1998): If a quantum algorithm makes T queries, its probability of accepting is a degree-2T multilinear polynomial over the x i s Right-to-Left Proof: Entries are now degree-1 polynomials over the x i sStill degree-1 polynomialsDegree-2 polynomialsAfter T queries, degree-T polynomials Thenhas degree 2T Implication: If a quantum algorithm computed x 1 x n with <n/2 queries, it would lead to a polynomial approximating PARITY with degree <n. Hence Deutsch-Jozsa must be optimal!

Another Famous Quantum Algorithm: Grovers Computes the OR of n bits using O( n) queries Is Grovers algorithm optimal? BBBV 1994: Yes, by a quantum argument Well instead prove Grover is optimal using … wait for it …

Theorem (Nisan-Szegedy 1994): Given a Boolean function f, let deg (f) be the minimum degree of a real polynomial p:R n R such that Observation: Is that lower bound tight? Yes, because of Grovers algorithm!

To prove deg (OR)= ( n), we need to revisit our good friend Markov… Theorem (Markov): If p is a degree-d real polynomial, then Another convenient form: for all n>0,

Markovs inequality is tight. The extremal cases are called the Chebyshev polynomials: Uhh … why is that a polynomial at all? which is a degree-d polynomial in cos x

Let p satisfy We want to lower-bound deg(p) Symmetrize: 0 1

0 1 One remaining problem: q(x) need not be bounded at non-integer x Solution: Notice So by Markovs inequality,

Collision Problem Problem: Given f:[n] [n], decide whether f is 1-to-1 or 2-to-1, promised its one or the other [A. 2002]: Any quantum algorithm needs (n 1/5 ) queries. Improved to (n 1/3 ) by Shi Illustrates the amazing reach of the polynomial method By the Birthday Paradox, ~ n queries to f are necessary and sufficient classically [Brassard et al. 1997] gave a quantum algorithm making O(n 1/3 ) queries

Lower bound by polynomial method Let Lemma (following Beals et al.): If a quantum algorithm makes T queries to f, the probability p(f) that it accepts is a degree-2T polynomial in the (x,h)s Now let be the expected acceptance probability on a random k-to-1 function

The Miracle: q(k) is itself a polynomial in k, of degree at most 2T

which is a degree-d polynomial in k. Thats why. Why? d3d3 d1d1 d2d2 d Technicality: Need to deal with k not dividing n

Another Useful Hammernomial: Bernsteins Inequality Application: Any quantum algorithm to compute the MAJORITY of n bits requires (n) queries Ouch, that really hurts the degree!

Oh, and dont forget the inequality of V. A. MarkovA. A.s younger brother! Application [A. 2004]: Direct product theorem for quantum search. After T queries, the probability that a quantum algorithm finds K marked items out of N is at most (cT 2 /N) K 01KN

3. POLYNOMIALS IN CIRCUIT COMPLEXITY

Linial-Mansour-Nisan 1993: If a Boolean function f is computable by an AC 0 circuit of size s and depth k, then we can find a degree-d real polynomial p such that Proof uses the Switching Lemma to upper-bound high-degree Fourier coefficients By Nisan-Szegedy, the above theorem would be false if we wanted |p(x)-f(x)| to be small for every x

Bazzi 2007: Let F=C 1 C m be a DNF formula. Then we can find degree-d real polynomials p and q such that Implies that polylog-wise independent distributions fool small DNFs. The proof takes 64 pages [Razborov 2008]

4. POLYNOMIALS EVERYWHERE

Polynomials in Oracle-Building Beigel 1992: There exists an oracle relative to which P NP PP Use the following problem: Given exponentially-long integers x=x 1 …x N and y=y 1 …y N, is x y? Its in P NP, since we can use binary search to find the leftmost i such that x i y i But is there a low-degree polynomial p such that

Sure: But by clever repeated use of Markovs inequality, one can show that any such polynomial must take on huge (doubly-exponentially-large) values This means the problem cant be in PP [A. 2006] generalized Beigels result to give an oracle relative to which PP has linear-size circuits Requires handling many polynomials simultaneously

Slide of Guilt: The Polynomial Method in Communication Complexity Razborov 2002: Any quantum protocol for the Disjointness problem requires ( n) qubits of communication Razborov and Sherstov, this very FOCS: An AC 0 function with large unbounded-error communication complexity Sherstov, this very FOCS: Characterizes the unbounded- error communication complexity of symmetric functions Chattopadhyay-Ada, Lee-Shraibman 2008: Lower bounds for the k-party communication complexity of Disjointness in the Number-On-Forehead model And more!

Some Positive Uses of Polynomials Harvey-Nelson-Onak, this very FOCS: Chebyshev polynomials used to give a streaming algorithm for approximating the Shannon entropy Beigel-Reingold-Spielman 1991: PP is closed under intersection

Future Direction 1: Beyond Symmetrization Find better techniques to lower-bound the degrees of multivariate polynomials. OR AND n n Upper bound: O( n) (from quantum algorithm) Lower bound: (n 1/3 ) (can be proved using the n 1/3 collision lower bound) deg(f)=O(deg (f) 2 ) for all Boolean functions f? Best known relation: deg(f)=O(deg (f) 6 ) (Beals et al.)

Future Direction 2: Understanding Bounded Real Polynomials Conjecture. Let p:R n [0,1] be a real polynomial of degree d. Suppose EX x,y [|p(x)-p(y)|]= (1). Then there exists an i [n] such that EX x [|p(x)-p(x i )|]= (1/poly(d)). Given a partial function f:S {0,1} (S {0,1} n ), let deg (f) be the minimum degree of a polynomial p such that (1) 0 p(x) 1 for all x {0,1} n, (2) |p(x)-f(x)| for all x S. Is there a partial f for which deg (f) is exponentially smaller than Q(f)? Would have major implications for quantum! e.g., for P vs. BQP relative to a random oracle

Future Direction 3: Matrix- Valued Polynomials Conjecture. Suppose max (A(x)) [0,1] for all x {0,1} n max (A(x)) 2/3 for all x encoding a 1-to-1 function max (A(x)) 1/3 for all x encoding a 2-to-1 function Then d 2 (d+log m)= (n). What Boolean functions can we approximate as Would imply an oracle relative to which SZK QMA (i.e., there are no succinct quantum proofs for problems like graph non-isomorphism)

Future Direction 4: Extending Bazzis Theorem to AC 0 (the Linial-Nisan Conjecture) Problem: Given f AC 0, construct polylog(n)-degree polynomials p,q:R n R such that If p,q have the further property that then we get an oracle relative to which BQP PH.

The polynomial method: the choice of hardworking American lowerboundsmen OPEN PROBLEM I approve!

Download ppt "The Polynomial Method In Quantum and Classical Computing Scott Aaronson (MIT) OPEN PROBLEM."

Similar presentations


text:
# Pushout of group schemes (question on a lemma in SGA3)

$$\DeclareMathOperator\GL{GL}\DeclareMathOperator\SL{SL}\DeclareMathOperator\diag{diag}$$In SGA3, Expose XXIV, Lemme 7.2.2 it says (let's say our base scheme $$S$$ is an algebraically closed field $$k$$): if $$G$$ is reductive algebraic group, $$T$$ a maximal torus, $$G'$$ the derived subgroup of $$G$$ and $$T' = T \cap G$$ a maximal torus of $$G'$$, then $$G$$ is a pushout of $$G'$$ and $$T$$ over $$T'$$ (even in the category of group sheaves).

Doesn't the following very basic example contradict this? Or what have I misunderstood?

Suppose $$G = \GL_2$$, $$G' = \SL_2$$, $$T$$ the diagonal torus and $$T'$$ the diagonal torus with determinant 1.

Define homomorphisms $$\alpha : T = \mathbb G_m^2 \to \GL_2$$ sending $$\diag(x,y)$$ to $$\diag(x,x^{-1})$$ and $$\beta : G' = \SL_2 \to \GL_2$$ the inclusion. Then $$\alpha$$ and $$\beta$$ agree on the intersection $$T'$$, but there is no homomorphism $$G = \GL_2 \to \GL_2$$ that restricts to $$\alpha$$ and $$\beta$$ because otherwise $$\alpha(\diag(x,x))$$ and $$\beta(y)$$ would commute for any $$x$$, $$y$$.

(See pages 39-40 of the pdf of Expose XXIV at the SGA3 Réédition project page, or the official published version)

The Lemma is clearly wrong. There is no way to recover $$G$$ from $$G'$$, $$T$$ and $$T'$$ alone (not even up to isomorphism) since that data do not determine the radical $$R:={\rm rad}(G)\subseteq T$$. Maybe the authors had in mind the amalgamated product of $$T$$ and $$R\times G'$$ over $$R\times T'$$.
• Thank you! That's a very good point: $GL_2$ and $SL_2 \times \mathbb G_m$ give rise to isomorphic pushout diagrams. – alpha101 Jun 21 at 20:24


text:
# In the poem 'wild nights' by emily dickinson, which correctly identifies the rhyme scheme of the poem? abab cdcd efef, abbb

###### Question:

In the poem "wild nights" by emily dickinson, which correctly identifies the rhyme scheme of the poem? abab cdcd efef, abbb cded fbgb, aabb ccdd eeff, abbb cddd efff

### What is one technological development in automobiles?

What is one technological development in automobiles?...

### Please help is due by 10:00 this morning (where i am at it is 8:18 am)

Please help is due by 10:00 this morning (where i am at it is 8:18 am) $Please help is due by 10:00 this morning (where i am at it is 8:18 am)$...

### You guys can add me on discord to talk by code is 4563 bored ash

You guys can add me on discord to talk by code is 4563 bored ash...

### Retained earnings: Group of answer choices Can only be appropriated by setting aside a cash fund. All

Retained earnings: Group of answer choices Can only be appropriated by setting aside a cash fund. All of the listed choices. Represent an amount of cash available to pay shareholders. Generally, consists of a company's cumulative net profit less any net losses and dividends declared since its inc...

### Which of these contains the most authoritative data on health and wellness? a.) a magazine article b.) a government study

Which of these contains the most authoritative data on health and wellness? a.) a magazine article b.) a government study c.) a social media survey d.) a diet advice book...

### Part B: Assume that the banner needs to be 18 feet long instead of 15 feet. How wide can it be to have

Part B: Assume that the banner needs to be 18 feet long instead of 15 feet. How wide can it be to have enough ribbon to go around? 1. Rewrite the inequality using an 18-foot length instead of 15 feet. (1 point) 2. Solve this inequality for w. (2 points) 3. Write your answer as a sentence. (1 point)...

### What is unusual about the school meal plan regarding the number of daily school mealsserved to each student? Why is it unusual?

What is unusual about the school meal plan regarding the number of daily school meals served to each student? Why is it unusual?...

### Evaluate the derivative of the given function for the given value of x. yequalsstartfraction 3 x minus 6 over 4 x plus 5

Evaluate the derivative of the given function for the given value of x. yequalsstartfraction 3 x minus 6 over 4 x plus 5 endfraction , xequals3...

### Given that f(x) = 2x + 1 and g(x) = the quantity of 3x minus 1, divided by 2 , solve for g(f( (5 points)

Given that f(x) = 2x + 1 and g(x) = the quantity of 3x minus 1, divided by 2 , solve for g(f( (5 points)...

### Mark feels the need to tap everything within his arms reach twice. He doesn't have any particular thoughts

Mark feels the need to tap everything within his arms reach twice. He doesn't have any particular thoughts associated with this, he just becomes anxious if he doesn't do it, because "something bad might happen." Mark...
Write the interval as an inequality. The (-4,8] Write the interval as an inequality....

### How were the ideals of Susan B. Anthony, Elizabeth Cady Stanton, and Sojourner Truth part of the development of the women's suffrage

How were the ideals of Susan B. Anthony, Elizabeth Cady Stanton, and Sojourner Truth part of the development of the women's suffrage movement?...

### Can someone tell me a disaster that happened in america in the ocean (besides deepwater horizon).

Can someone tell me a disaster that happened in america in the ocean (besides deepwater horizon)....

### Two doves upon the selfsame branch,Two lilies on a single stem,Two butterflies upon one flower:—O happy they who look

Two doves upon the selfsame branch, Two lilies on a single stem, Two butterflies upon one flower:— O happy they who look on them. Who look upon them hand in hand Flushed in the rosy summer light; Who look upon them hand in hand And never give a thought to night. —"Song," Christina Rossetti Use ...

### What is one reason that more affluent individuals may experience better health?

What is one reason that more affluent individuals may experience better health?...

### What would happen to bacteria if any of the FAT TOM conditions changed a lot?

What would happen to bacteria if any of the FAT TOM conditions changed a lot?...

### HELP URGENT!! Algebra Nation section 8 topic 6

HELP URGENT!! Algebra Nation section 8 topic 6 $HELPPPP URGENT!! Algebra Nation section 8 topic 6$...

### You are saving for a skateboard. Your aunt gives you $45 to start and you save$3 each week. The expression 45 + 3w gives

You are saving for a skateboard. Your aunt gives you $45 to start and you save$3 each week. The expression 45 + 3w gives the amount of money you save after w weeks. How much money will you have after 20 weeks? Is this enough money to buy the skateboard?...


text:
#### Economics of Development and Planning Two Marks Questions

12th Standard EM

Reg.No. :
•
•
•
•
•
•

Economics

Time : 00:45:00 Hrs
Total Marks : 30
15 x 2 = 30
1. Define economic development

2. Mention the indicators of development.

3. Distinguish between economic growth and development

4. Define economic planning

5. What are the social indicators of economic development?

6. Write a short note on NITI Aayog

7. What do you mean by New Welfare Oriented Approach?

8. Write any three non-economic factors

9. What do you mean by planning?

10. What is centralized planning?

11. What is human capital?

12. What is the idea of many economists about planning?

13. What is short term planning?

14. What is long term planning?

15. What are the two main approaches to the concept of development?


text:
Recently, I was looking to rent a server, either dedicated or virtual. I then compared the prices of several big players in this field, like DigitalOcean, AmazonWebServices, Azure, OVH and it's sub brands Kimsufi and SoYouStart, and many others, including Online.net know for it's Dedibox servers. While browsing Online.net's web site, I came across some cloud servers with really attractive prices, but they seemed to be provided by a partner named Scaleway. So I went there, to have a look. I wasn't really sure of what I would find, but it doesn't harm to add another competitor to the list. Here's what their home page looks like when I wrote this article.

#### A bit of history

Scaleway is the company that has been created from Online.net's labs. Basically, they created their own hardware to reduce the costs, increase the server density and hence decrease the prices. Here's a quote from their post about their public preview:

When we started the project, two years ago, we had a simple idea: create a platform thought for the cloud, not just an evolution of virtualization. We wanted to avoid the performance cost of virtualization. We wanted to be sure we would not get any performance impact from noisy neighbors.

(source)

Key moments: (found by crawling their blog)

Here is their presentation video, which I found interesting and funny:

#### The offer

Scaleway has two different offers : Dedicated and VPS servers. Their originality lies in the fact that they offer an ARM dedicated server, named C1 (they claim to be the firsts to do so). It has 4 cores, 2GB ram and 50GB SSD. The remaining part of their offer is more or less what we're used to see: x86 cores, good amount of memory, and for each server also 50 GB SSD. If you need more space, you may ask up to 150 GB, with 50 GB increments.

Volume are available per 50GB increments up to 150GB, with a maximum of 15 volumes per server.
Volumes are billed €1 /month per additional 50GB of SSD

Bare Metal Servers

VPS Servers

All plans comes with unlimited transfer, but the speed will depend on the plan you choose, starting from 200mbps, up to 800mbps for the most expensive server. They also state that if you're contacting another server located inside the datacenter, then you may use the full physical link speed (from 1 to 5 gbps), but only for bare metal servers. What's interesting here is that they bill everything individually : the IP address, the SDD and the server itself. This added flexibility is a good thing :

• If you want to upgrade to a bigger server, you may reuse your volume as if nothing changed.
• If you want to cancel your server but keep your data, you can (and even your IP if needed).
• If you want to make you server only available to other servers in the datacenter, you can release your IP (or explicitly ask not to have one when you create the server).

Another good thing: on the "Bare Metal" servers, you can mount up to 15 volumes at the same time. Sadly, this is not possible with the VPS ones, but they give an easy process to move from a vpn to a bare metal one. They also offer an Anti-DDoS, which is really nice for the price. If you upgrade your account (monthly fee required), you also get some bonuses like the access to the API, if you want to automate a bit your account, or priority support.

#### The pricing

All the prices are shown on the previous screenshots. Some of you may have noticed that the price per hour doesn't match the monthly price, because 720h * 0.002€/h = 1.44 €. But there's an explanation for this: to get the hourly price, you have to add the hourly price of the SSD, that is 0.002 €/h, and the price of the IP Address, also 0.002€/h, to the base server price. Here's my current "draft bill", for the server this web site is currently being hosted on: we can clearly see the three different prices for each resource.

Now you may say that there's another problem with this price : 1.44 € * 3 = 4.32 € and not 2.99 €. Well, in fact, there's another pricing rule. Once you use your server for more than 500h, the price is capped until the end of the month. And we can confirm this if we compute it ourselves : 0.002€/h * 3 (IP+Disk+Server) * 500 = 3.00 €. We finally got it ! This pricing might seem complex at the beginning, but there's no surprise in the end. Here are some excerpts from the documentation:

Phase 1: The resource is billed by the hour. Each additional hour of usage increase the total price of the resource.

Phase 2: Once a running resource reach the cap of 500 hours of continuous usage, the monthly rate is applied. The resource’s price is frozen to the fixed price for the rest of the month, and doesn’t increase your costs.

(EDIT 3 oct. 2018) Be careful: Restarting your server will reset the cap, as it's currently counted as continuous usage. If you have to restart, better do it at the beginning of the month.

(source)

#### Let's try it !

Now that we introduced our provider, let's give it a try. To create your account, you must give your credit card number, but that's a common practice among providers (DigitalOcean does that too, and some other providers). Once you're done, you'll get access to your control panel, that looks like this:

Creating a sever through the web interface is a smooth experience. There are only a few simple steps. Just don't forget to set your SSH key before creating your server, otherwise you won't be able to access it. But don't worry too much, if you don't, a big yellow popup will annoy you until you do so.

###### 1. Give it a name

Or use the default one.

###### 2. Choose the datacenter

Currently, you may only choose between either Paris (France) or Amsterdam (Netherlands).

###### 3. Choose which server you want

As you may see, each server has it's own product name, composed of some letters, which have the following meaning.

• "V" for "Virtual"
• "C" for "Compute"
• "S/M/L" for "Small/Medium/Large"

If a server is out of stock on a data center, you may want to check out the other one to see if it's available there. Currently, there's no C1 offering on the Amsterdam datacenter. But the server C2L is available there, whereas in Paris, it's out of stock.

###### 4. Choose what you want to install on it

You may install a raw linux distribution, or a ready-to-use image from the image hub (there are even more advanced options, but i'll let you find this out).

The currently available distributions:

The currently available images from the ImageHub:

As you can see there are many options. But it would have been nice to be able to have FreeBSD in the distributions, or a WordPress in the images. You may create you own image / snapshots to base your future servers on, but as I said before, i'll let you find out how to do so.

###### 5. Configure the last parameters

As you can see below, you may add more hard drives to your instance, enable IPv6, choose if you need to have a public IP, or even add some tags, if you feel fancy.

Once you're done, you'll see that the bottom bar updated to reflect your choices, and will display your final monthly price:

Once you're done, the system should take you to your server's page, were you'll be able to see it's current status and parameters. Here's what mine looks like:

##### Some interesting information

My current server is a VC1S. I installed Debian 8.2, and just the bare minimum : nodejs, ghost and MariaDB (dropin replacement for MySQL). I ran a network benchmark (a command line speedtest.net) and here are my findings:

root@scw-35de9f:/home/random# ./speedtest-cli
Retrieving speedtest.net configuration...
Retrieving speedtest.net server list...
Testing from Scaleway (163.172.152.32)...
Selecting best server based on latency...
Hosted by NEOTELECOMS (Paris) [1.88 km]: 3.099 ms

We seem to have 1gbps of download, and 230mbps of upload, which matches the advertised bandwidth of 200mbps. Now here's my cat /proc/cpuinfo of this server:

processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 77
model name      : Intel(R) Atom(TM) CPU  C2750  @ 2.40GHz
stepping        : 8
microcode       : 0x1
cpu MHz         : 2393.902
cache size      : 1024 KB
physical id     : 0
siblings        : 1
core id         : 0
cpu cores       : 1
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 11
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss syscall nx rdtscp lm constant_tsc arch_perfmon rep_good nopl pni pclmulqdq vmx ssse3 cx16 sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes rdrand hypervisor lahf_lm 3dnowprefetch tpr_shadow vnmi flexpriority ept vpid tsc_adjust smep erms arat
bugs            :
bogomips        : 4787.80
clflush size    : 64
cache_alignment : 64
address sizes   : 40 bits physical, 48 bits virtual
power management:

processor       : 1
(same as processor 0)

We can see that this server is having an Intel Atom C2750 (cpubenchmark: 3800), with 8 cores. You may have more information about this CPU by clicking on the links. I then used a nice tool to ping the server from different locations around the globe, and here are my findings :

#### Overall Experience

I found Scaleway's servers to be cheap and powerful enough for some simple websites. For example, with this blog, I'm using only 2-3% of the CPU, despite having the blog (nodejs+ghost) and MariaDB installed, on only 2 cores of an Intel Atom CPU. I also liked the management interface. It's clean and fast, and I got my server in less than a minute.

But there are some downsides. It misses some good features of OVH's manager, like the CPU usage / Memory graph directly integrated into the control panel. I also miss the possibility to have proper backups. Currently, you have to either use their snapshots system (which is a bit painful), or do it yourself. I'm going for the second one. But it would have been really nice if we could just buy a "backup" subscription, that does it automatically, but maybe this will come in the future, as the company is quite young.


text:
# Simple odd β-cycle inequalities for binary polynomial optimization

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd β-cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.

• 10 publications
• 11 publications
01/26/2018

### On bounded pitch inequalities for the min-knapsack polytope

In the min-knapsack problem one aims at choosing a set of objects with m...
12/29/2020

### Supermodularity and valid inequalities for quadratic optimization with indicators

We study the minimization of a rank-one quadratic with indicators and sh...
12/03/2019

### On the Shortest Separating Cycle

According to a result of Arkin  (2016), given n point pairs in the plane...
10/04/2019

### A Note on Directed Treewidth

We characterise digraphs of directed treewidth one in terms of forbidden...
07/15/2019

### A Simple Uniformly Valid Test for Inequalities

We propose a new test for inequalities that is simple and uniformly vali...
02/25/2017

### The natural algorithmic approach of mixed trigonometric-polynomial problems

The aim of this paper is to present a new algorithm for proving mixed tr...
02/03/2022

### A New Approach to Determine the Minimal Polynomials of Binary Modified de Bruijn Sequences

A binary modified de Bruijn sequence is an infinite and periodic binary ...

## 1 Introduction

In binary polynomial optimization

our task is to find a binary vector that maximizes a given multivariate polynomial function. In order to give a mathematical formulation, it is useful to use a hypergraph

, where the node set represents the variables in the polynomial function, and the edge set represents the monomials with nonzero coefficients. In a binary polynomial optimization problem, we are then given a hypergraph , a profit vector , and our goal is to solve the optimization problem

 max {∑v∈Vpvzv+∑e∈Epe∏v∈ezv:z∈{0,1}V}. (1)

Using Fortet’s linearization [12, 14], we introduce binary auxiliary variables , for , which are linked to the variables , for , via the linear inequalities equationparentequation

 zv−ze ≥0 ∀e∈E, ∀v∈e (2a) (ze−1)+∑v∈e(1−zv) ≥0 ∀e∈E. (2b)

It is simple to see that

 {z∈{0,1}V∪E:ze=∏v∈ezv ∀e∈E}={z∈{0,1}V∪E:(???)}.

Hence, we can reformulate (1) as the integer linear optimization problem

 max {∑v∈Vpvzv+∑e∈Epeze:(???), z∈{0,1}V∪E}. (3)

We define the multilinear polytope [6], which is the convex hull of the feasible points of (3), and its standard relaxation :

 \Pml(G) :=\conv{z∈{0,1}V∪E:(???)}, \Psr(G) :={z∈[0,1]V∪E:(???)}.

Recently, several classes of inequalities valid for have been introduced, including -link inequalities [4], flower inequalities [7], running intersection inequalities [8], and odd -cycle inequalities [5]. On a theoretical level, these inequalities fully describe the multilinear polytope for several hypergraph instances: flower inequalities for -acyclic hypergraphs, running intersection inequalities for kite-free -acyclic hypergraphs, and flower inequalities together with odd -cycle inequalities for cycle hypergraphs. Furthermore, these cutting planes greatly reduce the integrality gap of (3[8, 5] and their addition leads to a significant reduction of the runtime of the state-of-the-art solver BARON [9]. Unfortunately, we are not able to separate efficiently over most of these inequalities. In fact, while the simplest -link inequalities can be trivially separated in polynomial time, there is no known polynomial-time algorithm to separate the other classes of cutting planes, and it is known that separating flower inequalities is -hard [9].

### Contribution.

In this paper we introduce a novel class of cutting planes called simple odd -cycle inequalities. As the name suggests, these inequalities form a subclass of the odd -cycle inequalities introduced in [5]. The main result of this paper is that simple odd -cycle inequalities can be separated in strongly polynomial time. While our inequalities form a subclass of the inequalities introduced in [5], they still inherit the two most interesting properties of the odd -cycle inequalities. First, simple odd -cycle inequalities can have Chvátal rank . To the best of our knowledge, our algorithm is the first known polynomial-time separation algorithm over an exponential class of inequalities with Chvátal rank . Second, simple odd -cycle inequalities, together with standard linearization inequalities and flower inequalities with at most two neighbors, provide a perfect formulation of the multilinear polytope for cycle hypergraphs. Finally, we believe that our separation algorithm could lead to significant speedups in solving several applications that can be formulated as (1) with a hypergraph that contains

-cycles. These applications include the image restoration problem in computer vision

[4, 5], and the low auto-correlation binary sequence problem in theoretical physics [2, 15, 5, 18, 17].

### Outline.

We first introduce certain simple inequalities in Section 2 that are then combined to form the simple odd -cycle inequalities in Section 3. Section 4 is dedicated to the polynomial-time separation algorithm. In Section 5 we briefly address the question of redundancy since our inequalities are formally defined for a more general structure than a -cycle. Finally, Section 6 relates the simple odd -cycle inequalities to the general (non-simple) odd -cycle inequalities in [5].

## 2 Building block inequalities

We consider certain affine linear functions defined as follows.

 zv−ze ∀e∈E, ∀v∈e (since,v) ∀e∈E (sodde,U,W) ∀U,W:∅≠U,W⊆e, U∩W=∅ 2ze−1+∑u∈U(1−zu)+(1−zf)+∑v∈e∖(U∪f)(2−2zv) ∀e,f∈E:e∩f≠∅ (sonee,U,f) ∀U:∅≠U⊆e, U∩f=∅ 2ze−1+(1−zf)+(1−zg)+∑v∈e∖(f∪g)(2−2zv) ∀e,f,g∈E:e∩f≠∅, (stwoe,f,g) e∩g≠∅, e∩f∩g=∅

mm mmm mmm mmm In this paper we often refer to , , , as building blocks. Although in these definitions and can be arbitrary subsets of an edge , in the following and will always correspond to the intersection of with another edge. In the next lemma we will show that all building blocks are nonnegative on a relaxation of obtained by adding some flower inequalities [7] to , which we will define now. For ease of notation, in this paper, we denote by the set , for any nonnegative integer .

Let and let , , be a collection of distinct edges in , adjacent to , such that for all with . Then the flower inequality [7, 5] centered at with neighbors , , is defined by

 (zf−1)+∑i∈[m](1−zei)+∑v∈f∖∪i∈[m]ei(1−zv)≥0.

We denote by the polytope obtained from by adding all flower inequalities with at most two neighbors. Clearly is a relaxation of . Furthermore, is defined by a number of inequalities that is bounded by a polynomial in and .

###### Lemma 1.

Let be a hypergraph and let be one of , , , . Then is valid for . Furthermore, if and , then the implication given in Table 1 holds.

###### Proof.

First, is part of the standard relaxation and the implication is obvious.

Second, is the sum of the following inequalities from the standard relaxation: , for all , and . If and , then each of these inequalities must be tight, thus , for each . The last (tight) inequality yields , i.e., precisely one variable , for , is 0, while all others are 1, which yields the implication from Table 1.

Third, is the sum of the following inequalities: , for all and . The latter is the flower inequality centered at with neighbor . If and , then each of these inequalities must be tight, thus , for each . The last (tight) inequality yields , i.e., either and for exactly one , or and holds for all . Both cases yield the implication from Table 1.

Fourth, we consider . Note that due to , and , the three edges must all be different. Thus, is the sum of , for all and of . The latter is the flower inequality centered at with neighbors and . If and holds, then each of the involved inequalities must be tight, thus and for each . The last (tight) inequality implies , i.e., . ∎

## 3 Simple odd β-cycle inequalities

We will consider signed edges by associating either a “” or a “” with each edge. We denote by the set and by a sign change for . In order to introduce simple odd -cycle inequalities, we first present some more definitions.

###### Definition 2.

A closed walk in of length is a sequence ----------, where we have as well as and for each , where we denote and for convenience. A signature of is a map . A signed closed walk in is a pair for a closed walk and a signature of . Similarly, we denote , , and . We say that is odd if there is an odd number of indices with ; otherwise we say that is even. Finally, for any signed closed walk in , its length function is the map defined by

 ℓ(C,σ)(z)\coloneqq∑i∈I(+,+,+)(\sinceivi(z)+\sinceivi+1(z))+∑i∈I(−,−,−)\soddeiei∩ei−1ei∩ei+1(z)+∑i∈I(+,+,−)\sinceivi(z)+∑i∈I(−,−,+)\soneeiei∩ei−1ei+1(z)+∑i∈I(−,+,+)\sinceivi+1(z)+∑i∈I(+,−,−)\soneeiei∩ei+1ei−1(z)+∑i∈I(+,−,+)\stwoeiei−1ei+1(z),

where is the set of edge indices for which , and have sign pattern , i.e., .

We remark that the definition of is independent of where the closed walk starts and ends. Namely, if instead of we consider - ---------, and we define accordingly, then we have . Moreover, if or , then is independent of the choice of .

By Lemma 1, the length function of a signed closed walk is nonnegative. We will show that for odd signed closed walks, the length function evaluated in each integer solution is at least . Hence, we define the simple odd -cycle inequality corresponding to the odd signed closed walk as

 ℓ(C,σ)(z)≥1. (4)

We first establish that this inequality is indeed valid for .

###### Theorem 3.

Simple odd -cycle inequalities (4) are valid for .

###### Proof.

Let and assume, for the sake of contradiction, that violates inequality (4) for some odd signed closed walk . Since the coefficients of are integer, we obtain . From Lemma 1, we have that holds for all involved functions . Moreover, edge variables for all edges with , node variables for all nodes with , and the expressions for all nodes with are either equal or complementary (see Table 1), where the latter happens if and only if the corresponding edge satisfies . Since the signed closed walk is odd, this yields a contradiction for some edge of or for some node of or for a pair of subsequent edges of . ∎

Next, we provide an example of a simple odd -cycle inequality.

###### Example 4.

We consider the closed walk of length given by the sequence -------- with signature depicted in Figure 1. We have , , , , . The corresponding simple odd -cycle inequality is . Using Definition 2, we write in terms of the building blocks as

 ℓ(C,σ)(z)= \sonee1e1∩e5e2(z)+\since2v3(z)+\since3v3(z)+\sonee4e4∩e5e3(z)+\sodde5e5∩e4e5∩e1(z).

Using the definition of the building blocks, we obtain

 ℓ(C,σ)(z)= +2ze1−1+∑u∈e1∩e5(1−zu)+(1−ze2)+∑v∈e1∖(e1∩e5∪e2)(2−2zv) +(zv3−ze2)+(zv3−ze3) +2ze4−1+∑u∈e4∩e5(1−zu)+(1−ze3)+∑v∈e4∖(e4∩e5∪e3)(2−2zv) +2ze5−1+∑u∈e5∩e4(1−zu)+∑w∈e5∩e1(1−zw)+∑v∈e5∖(e5∩e4∪(e5∩e1))(2−2zv).

We write the sums explicitly and obtain

 ℓ(C,σ)(z) =+2ze1−1+(1−zv1)+(1−zu1)+(1−ze2) +(zv3−ze2)+(zv3−ze3) +2ze4−1+(1−zv5)+(1−ze3)+(2−2zu4) +2ze5−1+(1−zv5)+(1−zv1)+(1−zu1) =2ze1−2ze2−2ze3+2ze4+2ze5−2zv1−2zu1+2zv3−2zu4−2zv5+7.

Example 4 suggests that, when the function is written explicitly, the coefficients in the function exhibit a certain pattern. This different expression of is formalized in the next lemma. The proof of the lemma can be obtained directly from the definition of by summing up each variable that appears in more than one building block.

###### Lemma 5.

Given a signed closed walk in with , we have

 ℓ(C,σ)(z)=∑i∈[k]σ(i)=−(2zei+1)−∑i∈[k]σ(i)=+2zei+∑i∈[k]σ(i−1)=σ(i)=+2zvi+∑i∈[k]σ(i−1)=σ(i)=−v∈ei−1∩ei2(1−zv)+∑i∈[k]:σ(i)=−v∈ei∖(ei−1∪ei+1)2(1−zv)−2|{i∈[k]:σ(i−1)=σ(i)=−}|. (5)

Using Lemma 5, we obtain the following result.

###### Proposition 6.

Simple odd -cycle inequalities are Chvátal-Gomory inequalities for and can be written in the form

 ∑i∈[k]σ(i)=−zei−∑i∈[k]σ(i)=+zei+∑i∈[k]σ(i−1)=σ(i)=+zvi−∑i∈[k]σ(i−1)=σ(i)=−v∈ei−1∩ei(zv−1)−∑i∈[k]:σ(i)=−v∈ei∖(ei−1∪ei+1)(zv−1)≥1−|{i∈[k]:σ(i)=−}|2−|{i∈[k]:σ(i−1)=σ(i)=−}|. (6)
###### Proof.

Let be an odd signed closed walk in a hypergraph . From Lemma 1 we obtain that holds for each . Lemma 5 reveals that in the inequality , all variables’ coefficients are even integers, while the constant term is an odd integer. Hence, the inequality divided by has integral variable coefficients, and we can obtain the corresponding Chvátal-Gomory inequality by rounding the constant term up. The resulting inequality is the simple odd -cycle inequality (4) scaled by and has the form (6). This shows that simple odd -cycle inequalities are Chvátal-Gomory inequalities for . ∎

It follows from Proposition 6 that, under some conditions on , simple odd -cycle inequalities are in fact -cuts (see [3]) with respect to . Some classes of such cutting planes can be separated in polynomial time, in particular if the involved inequalities only have two odd coefficients. In such a case, these inequalities are patched together such that odd coefficients cancel out and eventually all coefficients are even. We want to emphasize that this generic separation approach does not work in our case since our building block inequalities may have more than 2 odd-degree coefficients. Nevertheless, the separation algorithm presented in the next section is closely related to the idea of cancellation of odd-degree coefficients.

## 4 Separation algorithm

The main goal of this section is to show that the separation problem over simple odd -cycle inequalities can be solved in strongly polynomial time (Theorem 10). This will be achieved by means of an auxiliary undirected graph in which several shortest-path computations must be carried out. The auxiliary graph is inspired by the one for the separation problem of odd-cycle inequalities for the maximum cut problem [1]. However, to deal with our different problem and the more general hypergraphs we will extend it significantly.

Let be a hypergraph and let . Define to be the set of potential subsequent edge triples. We define the auxiliary graph

 ¯G=(¯V,¯E)=(¯V+∪¯V−∪¯VE,¯E−,−,−∪¯E+,−,+∪¯E+,−,−∪¯E+,+,±)

and length function as follows.

 ¯V+\coloneqq V×{±} ¯V−\coloneqq {e∩f:e,f∈E, e≠f, e∩f≠∅}×{±} ¯VE\coloneqq E×{±} ¯E−,−,−\coloneqq {{(e∩f,p),(f∩g,−p)}:(e,f,g)∈\triples, p∈{±}} ¯ℓ{(U,p),(W,−p)}\coloneqq mine,f,g{\soddfUW(^z):U=e∩f, W=f∩g for some (e,f,g)∈\triples} ¯E+,−,+\coloneqq {{(e,p),(g,−p)}:e,g∈E,e∩f≠∅ and f∩g≠∅ for some f∈E with e∩f∩g=∅, p∈{±}} ¯ℓ{(e,p),(g,−p)}\coloneqq minf{\stwoefg(^z):f∈E, e∩f≠∅, f∩g≠∅, e∩f∩g=∅} ¯E+,−,−\coloneqq {{(e,p),(f∩g,−p)}:(e,f,g)∈\triples, p∈{±}} ¯ℓ{(e,p),(U,−p)}\coloneqq minf,g{\sonefUe(^z):(e,f,g)∈\triples, U=f∩g} ¯E+,+,±\coloneqq {{(v,p),(e,p)}:v∈e∈E, p∈{±}} ¯ℓ{(v,p),(e,p)}\coloneqq ???(^z)

We point out that the graph can have parallel edges, possibly with different lengths. We immediately obtain the following corollary from Lemma 1.

###### Corollary 7.

The edge lengths are nonnegative.

We say that two nodes are twins if they only differ in the second component, i.e., the sign. We call a walk in the graph a twin walk if its end nodes are twin nodes. For a walk in , we denote by the total length, i.e., the sum of the edge lengths along the edges in . In the next two lemmas we study the relationship between odd signed closed walks in and twin walks in .

###### Lemma 8.

For each odd signed closed walk in there exists a twin walk in of length , where is the slack of the simple odd -cycle inequality (4) induced by with respect to . In particular, if the inequality is violated by , then we have .

###### Proof.

Let be an odd signed closed walk with ----------. For , let be the product of signs of all edges up to . Moreover, define . For each , we determine a walk in of length at most , and construct by going along all these walks in their respective order. The walk depends on , and :

 ¯Wi\coloneqq⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩(vi,pi−1)→(ei,pi)→(vi+1,pi)if i∈I+,+,+(vi,pi−1)→(ei,pi)if i∈I+,+,−(ei,pi)→(vi+1,pi)if i∈I−,+,+(ei,pi)(length 0)if i∈I−,+,−(ei−1,pi−1)→(ei∩ei+1,pi)if i∈I+,−,−(ei−1∩ei,pi−1)→(ei+1,pi)if i∈I−,−,+(ei−1∩ei,pi−1)→(ei∩ei+1,pi)if i∈I−,−,−(ei−1,pi−1)→(ei+1,pi)if i∈I+,−,+.

The walks help to understand the meaning of the different node types: the walk starts at a node from if , it starts at a node from if , and it starts at a node from if holds. Similarly, the walk ends at a node from if , it ends at a node from if , and it ends at a node from if holds.

Note that all edges traversed by each are indeed in . It is easily verified that, for each , the walk ends at the same node at which the walk starts. Hence is indeed a walk in . Since holds, is closed and is odd, it can be checked that is a twin walk. Finally, by construction, holds, where the inequality comes from the fact that the minima in the definition of need not be attained by the edges from . By definition of we have , thus . ∎

###### Lemma 9.

For each twin walk in there exists an odd signed closed walk in whose induced simple odd -cycle inequality (4) has slack with respect to . In particular, if holds, then the inequality is violated by .

###### Proof.

Let be a twin walk in . We first construct the signed closed walk by processing the edges of in their order. Throughout the construction we maintain the index of the next edge to be constructed, which initially is . Since the construction depends on the type of the current edge (where visits first), we distinguish the relevant cases:

Case 1: and . Hence, and for some and some . We define and continue.

Case 2: and . Hence, and for some and some as well as . We define and . We then increase by and continue.

Case 3: and . Hence, and for some


text:
Discrete Mathematics

# Class 13: State Machines

### Schedule

There is no Problem Set due this week. Problem Set 6 will be posted soon and due next Friday (October 20) at 6:29pm.

Exam 1 was returned in class today. Please read the solutions posted in collab: Exam 1 Comments. If you didn’t pick up Exam 1 in class today, you can get it at Dave’s office hours tomorrow, or before or after class on Thursday.

## State Machines

A state machine is a binary relation (called a transition relation) on a set (both the domain and codomain are the same set). One state is designated as the start state.

$$M = (S, G: S \times S, q_0 \in S)$$

What does it mean if $G$ is total?

##

What does it mean if $G$ is not a function?

##

Parity Counter. Describe a state machine that determines if the number of steps is even.

#

Unbounded Counter. Describe a state machine that counts the number of steps.

#

How well do state machines model real computers? What kind of transition relation does the state machine modeling your computer have?

## State Machine Execution

An execution of a state machine $M = (S, G \subseteq S \times S, q_0 \in S)$ is a (possibly infinite) sequence of states, $(x_0, x_1, \cdots, x_n)$ where:

1. $x_0 = q_0$ (it begins with the start state), and
2. $\forall i \in {0, 1, \ldots, n - 1} \ldotp (xi, x{i + 1}) \in G$ (if $q$ and $r$ are consecutive states in the sequence, then there is an edge $q \rightarrow r$ in $G$)

A state $q$ is reachable if it appears in some execution. (That is, there is a sequence of transitions starting from $q_0$, following edges in $G$, that ends with $q$.)

$$M_1 = (S = \mathbb{N}, G = {(x, y) | y = x^2 }, q_0 = 1)$$ $$M_2 = (S = \mathbb{N}, G = {(x, y) | \exists k \in \mathbb{N} \ldotp y = kx }, q_0 = 1)$$

Which states are reachable for $M_1$ and $M_2$?

#