Mathematics

user193319

3:05 PM

Is it true that the elementary row operation of switching the $i$-th and $j$-th rows is implemented by the matrix $P_{ij} = I + E_{ij} + E_{ji} - E_{ii} - E_{jj}$? If so, what's the easiest way to argue that $P_{ij}$ is invertible?

Mary Star

Hello!!

We have that $\mathbb{Z}_{14}^{\star}=\{1,3,5,9,11,13\}$. From these elements we get the cyclic subgroups $\langle 1\rangle, \langle 13\rangle, \langle 3\rangle=\langle 5\rangle, \langle 9\rangle=\langle 11\rangle$. How can we show that $\mathbb{Z}_{14}^{\star}$ has no other subgroups?

Leaky Nun

3:28 PM

@MaryStar $(\Bbb Z/14\Bbb Z)^\times = (\Bbb Z/2\Bbb Z \times \Bbb Z/7\Bbb Z)^\times = (\Bbb Z/2\Bbb Z)^\times \times (\Bbb Z/7\Bbb Z)^\times = C_6$

in particular it is generated by $3$

Mary Star

You mean that $\mathbb{Z}_{14}^{\star}$ is a cyclic group that is generated by 3, right? @LeakyNun

Leaky Nun

sure

Mary Star

So we have that $ \langle 3\rangle=\langle 5\rangle=\mathbb{Z}_{14}^{\star}$. But how do we know that there are only the cyclic subgroups that I wrote above and no more? @LeakyNun

Leaky Nun

subgroups of cyclic groups are cyclic

Mary Star

Ah and since these are the only one that are created by the elements of $\mathbb{Z}_{14}^{\star}$ there are no other, right? @LeakyNun

Leaky Nun

3:40 PM

right

Mary Star

Great! Thank you!! @LeakyNun

Nick

what's the probability Logan Paul loses against KSI?

Mary Star

I have also an other question...

Let $Z = (\mathbb{Z},+)$ and $G = (M,\star)$ an arbitrary group. To show that for all $a\in G$ the map $\phi_a:Z\rightarrow G$ defined by $\phi_a(k)=a^k$ is an homomorphism from $Z$ to $G$, we have to show that $\phi_a(m+n)=\phi_a(m)\star \phi_a(n)$ for $m,n\in Z$. Why do we have to show also that $\phi_a$ is total ? Is it because we are given a map and we have to show first if it well defined?

Also I want to determine the range of $\phi_a$. It is the set $\{\phi_a(k)\mid k\in \mathbb{Z}\}=\{a^k\mid k\in \mathbb{Z}\}$, right? At the solution it is equal t…

Leaky Nun

what do you mean by total

also the solution is wrong about k >= 0

Mary Star

4:02 PM

Here is the defintion: https://en.wikipedia.org/wiki/Partial_function#Total_function

At the given solution the range is then equal to the cyclic group generated by a.

@LeakyNun

Leaky Nun

> Total function is a synonym for function. The use of the adjective "total" is to suggest that it is a special case of a partial function (specifically, a total function with domain X is a special case of a partial function over X). The adjective will typically be used for clarity in contexts where partial functions are common, for example in computability theory.

so no, you shouldn't use the word total here

and the solution is correct

the group generated by $a$ is $\{a^k \mid k \in \Bbb Z\}$

also who told you to show that the function is total?

Mary Star

At the given solution it is shown that the function is total: $a^k$ is for all k ∈ Z an element of G = (M,∗), since G = (M,∗) is a group and so closed.

Why do we have to show that? @LeakyNun

Leaky Nun

because the solution is stupid that's why

Mary Star

In that way they want to show that the given map is well defined, or not?

Leaky Nun

yes

Mary Star

4:12 PM

Ok. Thank you!

vzn

@MaryStar hi werent you working on a CS Msc awhile back?

Mary Star

@vzn Yes

vzn

@MaryStar are you in the middle of that?

Mary Star

@vzn I have finished, 2 years ago

vzn

@LeakyNun interested in those two esp connections to computability theory which seem to be existent but murky

@MaryStar did you do a Msc thesis? are you working on some math degree now?

Leaky Nun

4:19 PM

@vzn I thought there is no computable model of ZFC

vzn

@LeakyNun ah might have cited a recent paper on that in here by Yedidia-Aaronson. are inaccessible cardinals "outside of ZFC" in some sense? trying to remember some of this

Leaky Nun

I don't know in what sense

vzn

@LeakyNun lol so when are you going to start the "indoctrination"? :P

Leaky Nun

right after the message you quoted

vzn

so is it over already? missed it? :| :P

@user21820 there is some line of research crosscutting CS + math in applying SAT solvers to arbitrary problems that leads to insight not directly seen via other approaches.

Mary Star

4:25 PM

@vzn Yes, I did My Msc Thesis it is about Decidability in differential algebra (My Msc was in Maths of CS). Now I am teaching students and I want to deepen my knowledge also in some other topics of mathematics.

vzn

@MaryStar nice itd be great if you could post a link sometime... am interested in (un)decidability etc myself, have blogged on it etc eg vzn1.wordpress.com/2016/01/22/…

Mary Star

@vzn Ok

user21820

@vzn At least from what I know, the state-of-the-art SAT-solvers are all merely heuristic, and hence you don't get much qualitative insight into problems that you apply them to, since the point of using them is merely to solve the problem faster than a naive brute-force approach.

vzn

@LeakyNun inaccessible cardinals reminds me of paris-harrington thm & wonder if there is any connection en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem

Leaky Nun

@vzn I'm not the guy to ask this to :)

vzn

4:29 PM

@user21820 "heuristics" can be a tricky term. they sometimes outperform brute force searches because they can analyze "hidden structure" in the search space. there are nonw a few (relatively isolated/ scattered) cases of remarkable insights/ proofs related to them.

user21820

Heuristics that are tailored to a problem will in general be better than the best SAT-solvers. The advantage of using a SAT-solver is simply that you just have to find an efficient way of translating the problem to a SAT problem.

Shobhit

If X is a non-trivial topological vector space over F = set of reals , then the topology of X can never be discrete. Help me prove this please.

user21820

@vzn Citation needed. =)

vzn

@user21820 sometimes SAT solver heuristics outperform problem heuristics. heuristics are human inventions, SAT heuristics relate to machine learning in some sense.

user21820

@vzn That just implies that less effort went into the tailored heuristics than into the heuristics that underlie the SAT-solver, and hence does not invalidate my point.

vzn

4:32 PM

@user21820 there are at least 2 notable cases from last few yrs let me dig them up.

user21820

Sure.

vzn

@user21820 your point has some validity but the area is full of (deep/ hidden/ unexpected) nuances.

user21820

Yes my point is not something amenable to proof.

It is more of a personal heuristic observation. =P

vzn

@user21820 its an area of active research. imagine extremely sophisticated patterns being detected in the SAT formulation that a human couldnt detect, etc, there are graph-based analyses of the resulting SAT structures. have been looking/ dabbling into this for years...

user21820

@vzn That still suggests that a heuristic approach is better, just not being done 'efficiently' in the past. For example, humans can use graph visualization tools to help them understand the underlying graphs, while automatic analyzers will usually be unable to. If humans fail to use the tools available to an automated system, then the comparison would not be a 'fair' one.

Leaky Nun

4:37 PM

@Shobhit what does non-trivial mean?

user21820

Note that I'm not saying that it is always better to tailor heuristics. After all, SAT-solvers have been around a long time and a lot of effort has gone into them.

vzn

@user21820 ok the 2 relatively recent examples were the erdos discrepancy problem (since resolved by Tao) + pythagorean triples search. was recently reorganizing my links so have them around vzn1.wordpress.com/2016/09/16/… vzn1.wordpress.com/2014/02/14/…

user21820

So the benefit in tailoring heuristics must be weighed against the upfront costs.

@vzn Thanks! I'll take a look.

vzn

@user21820 not exactly disagreeing, but another way to see it is that the two approaches are complementary. machine learning is playing an increasing role across all sciences, and think it is making inroads into math, but more gradually there than hoped by me.

user21820

Yeap. I don't think we actually disagree.

Shobhit

4:39 PM

maybe $X = {0}$ @LeakyNun

user21820

Another example is gradient descent. It is one of the most common first-line approaches to attempting to solve 'somewhat' continuous optimization problems. Iterative improvement is similar. These very generic techniques will work to a certain extent, depending on the 'topography' of the potential function on the search space. But if the topography is more discontinuous, then heuristics become increasingly superior, for the same investment in human intelligence.

vzn

@user21820 theres the trees vs forest. gradient descent is far more than what anyone realizes. on a higher level its involved in self driving cars, conquest of Go by deepmind, etc... so it sometimes comes down to how the problem is formulated by humans.

user21820

@vzn Go is played well only because a ton of processing power was chucked at it. That merely strengthens my point.

When a computer that has the same rate of energy consumption as a human beats a professional Go player, I will sit up and take notice.

vzn

@user21820 there is some point to be made but its subtle. the point is that a relatively primitive technique formulated centuries ago (on single variate functions!) can be applied in entirely new ways, not all has been squeezed out of it yet, surprises, even very big ones, likely remain.

user21820

@vzn This is true, but a lot of these convergence results (that prove that certain optimization algorithms on certain classes of problems will always converge on the optimal solution as time goes to infinity) are simply too slow in practice, even though they have one benefit over trying to tailor heuristics: you don't have to think to use them.

As I said, I will take notice only when computers become more intelligent than humans at the same power consumption.

vzn

4:47 PM

@user21820 "you dont have to think to use them." bug or feature? :P

user21820

@vzn I was trying to give one advantage of such techniques, so... feature.

vzn

@user21820 there are some reasonable estimates that supercomputers (GPU clusters, cloud computing etc) are getting close to human hardware computational capability.

user21820

=P

@vzn What do you mean by that? I said power consumption. Not computational capacity.

vzn

@user21820 lol human brain consumes ~20W less than a typical hairdryer :P

user21820

That is exactly what I'm driving at. Our limitations are because we are just TOO slow.

vzn

4:50 PM

@user21820 "limitations"? thought you just asserted humans can outdo gradient descent :P

Oskar Tegby

@Ted I'm a bit stuck. I don't get the $x_n$ thing. Does that depend on $N$? Does the interval grow smaller as $n$ grows larger since $x_n=\frac{1}{\sqrt{n}\to0$ for $n\to\infty$?

vzn

@user21820 so even if AGI is achieved, you will not be impressed or "take notice" if it takes more than 20W? :P

user21820

@vzn Correct in a sense. More precisely, if you use a gradient descend algorithm with some mechanisms to get out of local minima, such as using simulated annealing, then we have theoretical proof that it converges to the global optimum, and you will observe its performance gradually improving over time.

In contrast if you put a human against the same problem, that human will have to spend a certain amount of time for each improvement to his/her heuristic. So performance will increase only in jumps, and depending on significant time and effort, but eventually will outdo the generic optimization algorithm.

@vzn The comparison will be by total energy usage. So you can give the computer more power but less time.

vzn

@user21820 to some degree maybe an apples vs oranges comparison... personally think an (eventual) AGI algorithm will probably incl some gradient-descent like logic, how about that?

user21820

@vzn Perhaps.

Secret

4:59 PM

PhD stuff: molecules keep rolling to the wrong saddle points

ugh

I will need a heavy dose of inaccessibles to refresh my mind, perhaps even a little bit reading the QED logic book

vzn

@user21820 another one of my fave refs, undeservably obscure gem, Decomposing Satisfiability Problems by Herwig citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.1116

Transcript for

$Mathematics$ Mathematics