text:
mersenneforum.org > YAFU SNFS of C112 cofactor of 608^60+480^76
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-05-17, 21:20 #1 sean     Aug 2004 New Zealand 3418 Posts SNFS of C112 cofactor of 608^60+480^76 I've been trying to complete 608^60+480^76 by SNFS using yafu. I first took out the obvious 2^300, then generated a degree 5 polynomial from (19^12)^5+15(2^16 * 5^75)^5. There is also a small factor 193. My input looks like: Code: n: 1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657 m: 938653510572529699833798948683334366050403278236720135828886826556700342961769485489321955075594682751310365305 deg: 5 skew: 1.718 type: snfs c5: 1 c0: 15 Y0: -2213314919066161 Y1: 28697814000000000000000 rlim: 588500 alim: 588500 lpbr: 25 lpba: 25 mfbr: 47 mfba: 47 rlambda: 2.3 alambda: 2.3 When I run yafu, sieving appears to proceed well with good yield etc. Yet when it gets to filtering things go awry, the nfs.log is full of messages like Code: Wed May 17 20:14:24 2017 error -11 reading relation 0 Wed May 17 20:14:24 2017 error -11 reading relation 1 Wed May 17 20:14:24 2017 error -11 reading relation 2 ... My first thought was that there must have been some corruption of files left over from a previous run. So I repeated the whole thing in a clean directory and the same thing happened. It only takes half an hour or so do the sieving. My next suspicion is that there is something wrong with my polynomials. Any ideas?
2017-05-17, 21:42   #2
RichD

Sep 2008
Kansas

23×431 Posts

Quote:
 Originally Posted by sean My first thought was that there must have been some corruption of files left over from a previous run. So I repeated the whole thing in a clean directory and the same thing happened. It only takes half an hour or so do the sieving. My next suspicion is that there is something wrong with my polynomials. Any ideas?
In the second term 480 = 2^5 * 3 * 5.
It appears you forgot the 3^75.

Edit: Actually it should be 3^15 * 5^15 if raised to the fifth power.

Last fiddled with by RichD on 2017-05-17 at 21:44

2017-05-17, 21:47   #3
sean

Aug 2004
New Zealand

32·52 Posts

Quote:
 Originally Posted by RichD In the second term 480 = 2^5 * 3 * 5. It appears you forgot the 3^75. Edit: Actually it should be 3^15 * 5^15 if raised to the fifth power.
Ugh! Sorry, that was typo in my explanation, that should read (19^12)^5+15(2^16 * 15^15)^5, giving
2^16*15^15 = 28697814000000000000000.

So although my formula in explanation was wrong, I think I have the correct value in my polynomial.

 2017-05-17, 21:50 #4 RichD     Sep 2008 Kansas 23·431 Posts After further review, I think it should be 2^30 * 15^15. Edit: Never mind. I can't do math. You are correct. Last fiddled with by RichD on 2017-05-17 at 22:03
2017-05-17, 22:07   #5
sean

Aug 2004
New Zealand

32·52 Posts

Quote:
 Originally Posted by RichD After further review, I think it should be 2^30 * 15^15.
Thanks for your time looking at this, but 2^30 * 15^15 doesn't work: not a common root of the polynomial.

How did you get 2^30?

I'm seeing it like this 480^76 = 2^(5*76) * 3^76 * 5^76. Then remove 2^300, to get 2^80*3^76*5^76 = 15*(2^16*15^15)^5.

 2017-05-17, 23:10 #6 swellman     Jun 2012 320310 Posts You could let Yafu choose the poly automatically, for comparison purposes. It will almost certainly choose the same poly as you but adds parameters etc as required by yafu for sieving. Maybe something will show up that is missing, like "size:" (I don't think yafu requires that parameter but I'm not sure). It is missing from your nfs.job file. Code: nfs(1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657) -v
2017-05-17, 23:22   #7
sean

Aug 2004
New Zealand

22510 Posts

Quote:
 Originally Posted by swellman You could let Yafu choose the poly automatically, for comparison purposes. It will almost certainly choose the same poly as you but adds parameters etc as required by yafu for sieving. Maybe something will show up that is missing, like "size:" (I don't think yafu requires that parameter but I'm not sure). It is missing from your nfs.job file. Code: nfs(1512787865815604665168125992005458173124947471321097315052908880093889444629900995273034048975712989271411140657) -v
If I try the above, yafu starts searching for a polynomial as a GNFS job. I know that wouldn't take that long for this number, but I'm curious why the SNFS approach is not working.

I've done a bunch of somewhat similar cases without problem, but there must be something unusual or special about this one or some error I've made in my polynomials. I have yafu, v1.34.5.

 2017-05-17, 23:41 #8 RichD     Sep 2008 Kansas 23×431 Posts I removed the parameters and ran the poly through factMsieve and it factored it into p44 * p68. factMsieve used similar parameters so nothing wrong with the poly. If you want the solution I can post to FDB but I'm sure you want to solve the problem resolve the issues because you may have other similar numbers of this size. Last fiddled with by RichD on 2017-05-17 at 23:48 Reason: clarification
 2017-05-17, 23:43 #9 swellman     Jun 2012 3,203 Posts Yeah I guess your composite is not derived from the forms yafu checks during SNFS poly selection, so it defaults to GNFS. Well if your poly was incorrect yafu would quickly crash. Since that is not happening, the poly works. The only thing missing is a line size: 200 (or whatever the difficulty is for this composite). Try adding the size? Also, you don't need deg: 5. Yafu probably ignores it, but maybe it's causing problems? ETA: the recent ggnfs sievers sometimes act strangely for me when I do small jobs like this. Maybe try with an older version of ggnfs? Last fiddled with by swellman on 2017-05-17 at 23:46
2017-05-18, 01:34   #10
sean

Aug 2004
New Zealand

32·52 Posts

Quote:
 Originally Posted by RichD I removed the parameters and ran the poly through factMsieve and it factored it into p44 * p68. factMsieve used similar parameters so nothing wrong with the poly. If you want the solution I can post to FDB but I'm sure you want to solve the problem resolve the issues because you may have other similar numbers of this size.
Thanks for that. I've now replicated the run using factMsieve (I'd never used that before) and was able to factor as you indicated.

I tried various other things around the job file for yafu, including the suggestions of swellman, but I still couldn't get it to work -- and I'm sick of trying various combinations now. Since both are pointing at the same underlying siever, I can only assume it must be some issue with the filtering in yafu.

I've actually found a second case where yafu does the same thing, so I will try doing that one with factMsieve as well.

 2017-05-18, 02:15 #11 swellman     Jun 2012 3,203 Posts This is a puzzling bug. I'll try to duplicate it tomorrow once I'm back in front of a computer. I've got a bunch of computers with different versions of yafu, giving a nice cross section of environments. Maybe something will turn up. Have you tried compiling the dev branch of yafu discussed here? Apparently a lot of bugs fixed, maybe this one too? Last fiddled with by swellman on 2017-05-18 at 02:15

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Information & Answers 4 2016-12-12 04:35 pinhodecarlos NFS@Home 2 2016-10-18 17:43 literka Factoring 7 2012-04-05 09:51 fivemack Factoring 45 2012-02-14 08:50 MatWur-S530113 PrimeNet 9 2010-02-16 12:52

All times are UTC. The time now is 13:09.

Thu Oct 21 13:09:54 UTC 2021 up 90 days, 7:38, 1 user, load averages: 1.50, 1.42, 1.36


text:
# Package doclicense gives error with hyperxmp; PDF is produced

Compiling the following MWE:

\documentclass{article}

\usepackage[
type={CC},
modifier={by-sa},
version={4.0},
lang={spanish}

\usepackage{lipsum,siunitx}

\begin{document}

\lipsum[1-3]

\end{document}

When I compile I get the follwing error:

! Undefined control sequence.
<argument> \hyxmp@dc@lang

However, even with the error, a PDF is produced. How does one get rid of the error? This started happening after my last TeXLive upgrade; current version is 2020.20200925-1 (running on Debian Testing); doclicense is version 2.2.1.dev.

The doclicence package says that it requires hyperxmp. However, your code would not run for me unless I explicitly loaded hyperxmp under v2.2.0 of doclicense. When I updated to v2.2.1 of doclicense the issue went away. (I have v5.4 of hyperxmp.)

\documentclass{article}

\usepackage[
type={CC},
modifier={by-sa},
version={4.0},
lang={spanish}

By loading hyperxmp explicitly, I got the output shown below with v2.2.0 of doclicense:
• Right! I suppose the version I have of doclicense is still "in development", because it says it is v.2.2.1.dev. This works; what I don't understand is why now, I had been working with files using doclicense before without this error. Thanks! – mathbekunkus Oct 7 '20 at 3:51

format: plain


text:
# zbMATH — the first resource for mathematics

Fine topology on function spaces. (English) Zbl 0614.54014
The author studies certain fine topologies that can be imposed on the space C(X,Y) of all continuous mappings from a Tikhonov space X into a uniform Tikhonov space Y. From the observation that the uniformity on Y induces a uniformity on C(X,Y) he proceeds to derive a number of results of which the following will give some idea of their scope. If X is compact, then all compatible uniformities on Y will generate the same topology on C(X,Y), namely, the compact-open topology. If Y is completely metrizable, then C(X,Y) with the fine uniform topology induced by the fine covering uniformity on Y will be a Baire space. In case Y is the real line with metric $$\rho\leq 1$$, the author writes C(X) for C(X,Y) and denotes by $$C_{f\rho}(X)$$ the topology generated under translation by neighborhoods of the zero-function $$f_ 0$$ having the form $$\{$$ $$g\in C(X):\rho (g(x),0)<\phi (x)$$ for all $$x\in X\}$$ as $$\phi$$ runs over the continuous mappings from X into the positive real numbers. If X is normal and $$f_ 0$$ has a countable base in $$C_{f\phi}(X)$$, then X must be countably compact. Finally, if C(X) is first countable in the fine uniform topology, then X must be pseudocompact.
Reviewer: J.V.Whittaker

##### MSC:
 54C35 Function spaces in general topology 54E15 Uniform structures and generalizations 54D65 Separability of topological spaces
##### Keywords:
compact-open topology; fine uniform topology; Baire space
Full Text:


text:
# Solve for $x$ in $[-\pi,\pi]$

Solve for $x$ in $[-\pi,\pi]$
$\cos x=\frac{-\sqrt{3}}{2}$

If I look up above Unit Circle,I can see that $\cos x=\frac{-\sqrt{3}}{2}$ is $\frac{5\pi}{3}$ but the right answer is $\frac{-5\pi}{6}$ or $\frac{5\pi}{6}$

-
Just read: for $x=5\pi/3$, $\cos(x)=1/2$, not $-\sqrt3/2$. – Did May 1 '12 at 12:46
ok! i got it one, but the other is when I look to $\frac{-\sqrt{3}}{2}$ it is not cos anymore, it is in $sin$ area. – Sb Sangpi May 1 '12 at 12:55
The x in "cos x" is NOT the same as the x of the horizontal axis or of the ordered pair (x, y). This can be confusing. The point where angle t, in standard position, crosses the unit circle is $(\cos t, \sin t)$. I would recommend "Solve for t in $[-\pi, \pi]$"... – The Chaz 2.0 May 1 '12 at 13:04
@TheChaz so does the $x$ mean green lines from the above graph.thx – Sb Sangpi May 1 '12 at 13:13
@SbSangpi: The facts $\cos(-\theta)=\cos(\theta)$ and $\sin(-\theta)=-\sin(\theta)$ are useful. – André Nicolas May 1 '12 at 14:48

You want to find all the values of $x \in [-\pi, \pi]$ for which $\cos(x) = \frac{-\sqrt{3}}{2}$. This means that you want to find the $x$-coordinates on the unit circle for which this holds, but they have to be in the interval $[-\pi, \pi]$
Let's consider $[0, \pi]$, the upper half of the unit circle. By looking at the unit circle, we have $\cos(x) = \frac{-\sqrt{3}}{2}$ (the $x-$coordinate is $\frac{-\sqrt{3}}{2}$) at $\frac{5 \pi}{6}$.
Now, let's consider $[-\pi, 0]$, the lower half of the unit circle. $\cos(x) = \frac{-\sqrt{3}}{2}$ at $\frac{7 \pi}{6}$, but this isn't part of the interval $[-\pi, 0]$. However, since $\frac{7 \pi}{6} = \frac{7 \pi}{6} - 2\pi = -\frac{5 \pi}{6}$, and this is part of the interval $[-\pi, 0]$, $-\frac{5 \pi}{6}$ is the second value that satisfies your equation.


text:
# Is it possible to find a non-cut vertex in O(|V|) time?

Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a cut vertex if removing this vertex with its incident edges from $G$ makes the graph disconnected. Finding a cut-vertex can be done in linear time.

My question is as follows: is it possible to find a non-cut vertex in $O(|V|)$ time?

My idea is to find a spanning tree of $G$, since all leaves of the spanning tree are non-cut vertices. However, I cannot find a spanning tree in $O(|V|)$ time.

Although I can find a cycle in $O(V)$ time, finding a non-cut vertex in a cycle seems not obvious to me.

I am wondering whether this problem has been solved, and I would appreciate any pointers provided by anyone.

• I'm confused by something in your question. Isn't every vertex of a simple cycle a non-cut vertex? Also, what is your model of computing that allows computation in time that doesn't depend on $E$? Are you only allowed to query adjacency between pairs of vertices, or can you list edges incident to a vertex? – David Eppstein Feb 1 '16 at 21:11
• @DavidEppstein Pick the graph defined by $a \leftrightarrow b \leftrightarrow c \leftrightarrow d$ and $b \leftrightarrow e \leftrightarrow c$. $c$ is a vertex of the cycle $(a,b,c)$, but removing it disconnects the graph: $a$, $b$ and $e$ on one hand and $d$ alone. – Boson Feb 1 '16 at 23:33
• Ok, thanks, that answers that question. But again, what is the model of computing? – David Eppstein Feb 1 '16 at 23:52
• @DavidEppstein The graph is represented by an adjacency list. – Yu-Han Lyu Feb 2 '16 at 0:47
• I didn't say finding a cut vertex can be done in $O(|V|)$ time. A cut vertex can be found in linear, $O(|V| + |E|)$, time. – Yu-Han Lyu Feb 3 '16 at 15:12

It's not possible for a deterministic algorithm: an adversary can always either fool the algorithm or make it look at $\Omega(n^2)$ entries of the adjacency lists.
Let $H$ be a disjoint union of two $n/4$-regular complete bipartite graphs. The adversary will remove a path of three vertices (not revealed to the algorithm) from each of the two components of $H$, and then replace these four removed edges by a different four edges that reconnect the two components, preserving $n/4$-regularity. It can do this in either of two ways:
• Swapping the middle vertices of each path results in a graph $H'$ with no non-cut vertices.
• Replacing one path by an edge connecting its endpoints, and splicing its former middle vertex into the interior of the other path, results in a graph $H''$ with one cut vertex. The cut vertex can be made to be either of the two former middle vertices.
However, by employing the strategy of making the removed path be in the last place the deterministic algorithm will look for it, it can force the algorithm to either not find the path (and not be able to distinguiish $H'$ from $H''$) or examine $\Omega(n^2)$ edges of the graph. In particular, as long as it is possible to answer a query (what is the $i$th entry of the adjacency list for vertex $v$) consistently with $H$, the adversary does so. Once the adversary is forced to choose the remaining path edges, it makes this choice arbitrarily, along with the choice of $H'$ or $H''$, and then answers the remaining queries according to the choice it made.
In order to force the adversary to choose between $H'$ or $H''$, the deterministic algorithm must see a set of edges that covers all two-edge paths on at least one of the two components on $H$. But each component of $H$ has $\Omega(n^2)$ disjoint two-edge paths, so the deterministic algorithm must see $\Omega(n^2)$ edges before it covers them all. And if it doesn't force the adversary to choose, then it is unable to distinguish graphs that have a cut vertex from those that don't, or to tell which vertex is the cut vertex.


text:
# My Newtonmass Fractal

I like the hyperbolic tangent function. It is useful for making sigmoid curves for neurons and fitting growth rates, it enables a cute minimal surface. So of course it should be iterated to make fractals! And there is no better way to celebrate Newtonmass than to make fractals!

As iteration formula I choose $z_{n+1} = f(z_n) = \tanh(cz_n)$ , where c is a multiplicative constant. Iterating some number like 1 and plotting its fate produces the following “Mandelbrot set” in the c-plane – the colours here do not denote the time until escape to infinity but rather where in the complex plane the point ended up, as a function of c. In a normal Mandelbrot set infinity is an attractive fixed point; here it is just one place in the (extended) complex plane like any other.

The pinkish surroundings of the pattern represent points attracted to the positive solution of $z=\tanh(cz)$. There is of course a corresponding negative solution since tanh is antisymmetric: if z is an attractive fixed point or cycle, so is -z. So the dynamics is always bistable.

Incidentally, the color scheme is achieved by doing a stereographic projection of the complex plane onto a sphere, which is then fitted into the RBG cube. Infinity corresponds to (0.5,0.5,1) and zero to (0.5,0.5,0) – the brownish middle of the Mandelbrot set, where points are attracted towards zero for small c.

Another property of tanh is that the function has singularities wherever $z=\pm \pi n i / 2 c$ for integer $n>0$. Since Great Picard’s Theorem, that means that in the vicinity of those points it takes on nearly all other values in the complex plane. So whatever the pattern of the corresponding Julia set is, it will repeat itself near there (including images of the image, and so on).This means that despite most z points being attracted towards zero for c-values inside the unit circle, there will be a complex stitching of undefined points since they will be mapped to infinity, or are preimages of points that get mapped there.

Zooming into the messy regions shows that they are full of circle-cusp areas where there is a periodic attractor cycle. Between them are the regions where most of the z-plane where the Julia sets live is just pure chaos. Thanks to various classic theorems in the theory of complex iteration we know that if the Julia set has non-empty interior it is the entire complex plane.

Walking around the outside edge of the boring brown circle gives a fun sequence of patterns. At $c=1$ there are two real fixed points and a straight line border along the imaginary axis. This line of course contains the singularity points where things get sent to infinity, and near them the preimages of all the other singularities on the line: dramatic, but visually uninteresting.

As we move along the circle towards more imaginary c, there is a twisting of the border since each multiplication by c corresponds to a twist: it is now a fractal spiral covered by little spirals. As the twisting gets stronger, the spirals get bigger and wilder (especially when we are very close to the unit circle, where the dynamics has a lot of intermittency: the iterates almost but not quite gets stuck close to certain points, speed away, and then return to make rather elliptic spirals).

When we advance towards a cuspy border in the c-plane we see the spirals unfold into long twisty tentacles just before touching, turning into borders between chains of periodic domains.

But then the periodic domains start to snake out, filling the plane wildly.

until we get a plane-filling, ergodic Julia set with no discernible structure. For some c-values there are complex tesselations of basins of attraction, and quite often some places are close enough to weakly repelling fixed points to produce small circular false basins of attraction where divergence is slow.

One way of visualizing this is to make a bifurcation diagram like we do for real iteration. Following a curve $r e^{i\theta}$ we plot where iterates end up projected along some line (for example their real or imaginary part, or some combination). To make structure stand out a bit more I decided to color points after where in the whole plane they are, producing a colorful diagram for r=1.1:

(I have some others on Flickr for the imaginary axis, r=1.25 and r=1.5).

Another, more fun way is to turn them into animated gifs. Since Flickr doesn’t handle them well, I have stored them locally instead:

• Growth of the Mandelbrot set – shows the behaviour of test iterates in the c-plane near the edge. Note the intermittent spirals.
• Unit circle – following the unit circle.
• Tanh 1.0 – the same as above, but inverted coordinates: $z=\infty$ is at the center, zero outside the borders.
• Tanh 1.1 – r=1.1.
• Tanh 1.5 – r=1.5.
• Tanh 2.5 – r=2.5.
• Tanh 5.0 – r=5.0. Rather sedate except for a brief window near $\theta=\pi/2$.

Note how spirals unfold until they touch each other, forming periodic domains or exploding across the entire plane, making a chaotic full-plane attractor… which often blinks into complex patterns of periodic domains only to return to chaos.


text:
# What do the square brackets mean in $[5-(6-7(2-6)+2)]+4$?

While watching a youtube video about a Simpsons math episode at 1:27 there's a puzzle that includes square brackets.

$$[5-(6-7(2-6)+2)]+4$$

Apparently the answer is $-27$ which I can't figure out how to arrive at that answer. I've Googled that the square brackets mean intervals. But then I don't understand the context of this question as surely an interval should be two numbers separated by a comma?

How do you arrive at $-27$?

• They mean the same than the parantheses, they're just there for better readability. Feb 21, 2016 at 7:59
• Square brackets, "curly" brackets, and (so help me) occasionally even diagonal brackets are used as alternatives to parentheses when too many nested parentheses might make it hard to tell which "block" of symbols is "inside" which delimiters. As for the notation you saw on your Google search, a closed interval would contain two numbers separated by a comma, thus $\ [ a \ , \ b ] \$ and is "interval notation" for the "inequality notation" $\ a \ \le \ x \ \le \ b \$ . Feb 21, 2016 at 8:05
• Square and round brackets are also used to denote intervals, and round brackets are also used to denote ordered pairs. And you will also see $(x_n)_n$ which means $(x_n)_{n\in N}$ which means the sequence $(x_1,x_2,x_3,...)$ Feb 21, 2016 at 11:04

In this case, it is a matter of legibility; the square brackets are the same as round parentheses;

$$[5-(6-7(2-6)+2)]+4 = [5-(6-7(-4)+2)]+4 = [5-(6+(28)+2)]+4 = [5-(36)]+4 = [-31+4] = -27.$$ Note that there are instance where the square brackets do mean something different like nearest integer function.

Yes, interval notation must contain a comma;
for example, if $a,b\in \mathbb R$, then $$[a,b] = \{x\in \mathbb R:a\leq x\leq b\}.$$

• Can't believe I've never seen a mix of different bracket types as parenthesis before. I wonder if it's a UK / US difference of preference thing, although I've been googling that and can't find anything.
– Ally
Feb 21, 2016 at 8:28
• Some answers are very good however I must accept one and since you've added an explanation on where square brackets can mean something different I think this is the best answer. Thanks
– Ally
Feb 21, 2016 at 8:30
• It's not a UK/US thing. Brackets are used the same way all over the world. Feb 21, 2016 at 8:41
• @Ally I believe there is a convention: Use square brackets on the out most nesting and parentheses on the inner most nestings. However, I don't believe it's a hard and fast rule. Also, you might see a mix with braces too when evaluating an expression, like $[2+3(8-\{4-2\})]$. Again, the brackets/parentheses/braces would mean the same thing. I do not believe it is a matter of UK/US custom; you'll see commonly see it if you study more math. Thanks for accepting. I would not have answered if I did not believe I could contribute something else/extra. Good luck.
– Em.
Feb 21, 2016 at 8:44
• @SS_C4 I am quite susceptible to typographical errors, hehe. Thanks.
– Em.
Feb 21, 2016 at 10:06

It’s just a parenthesis; the use of square brackets instead of round is to make it easier to match up corresponding left and right brackets.

\begin{align*} [5-(6-7(2-6)+2)]+4&=[5-(6-7(-4)+2)]+4\\ &=[5-(6-(-28)+2)]+4\\ &=[5-(6+28+2)]+4\\ &=[5-36]+4\\ &=-31+4\\ &=-27 \end{align*}

This is simple arithmetic. The square brackets here just indicate that the expressions inside them must be evaluated first. $$[5-(6-7(2-6)+2)]+4=[5-(6-7(-4)+2)]+4=[5-(6+28+2)]+4=[5-(36)]+4=[-31]+4=-27$$

The square brackets mean here just regular parentheses. To make it easily readable the outer parentheses sometimes are substituted to square and the curly brackets. As for the result, start with innermost parentheses and you will get the desired answer.

Square brackets in this context mean the same thing as round parentheses. Would it help you if it was written as $$\left(5-(6-7(2-6)+2)\right)+4=5-(6+28+2)+4=5-36+4=-27$$ You can probably see why they are used from this; as too many $\color{red}{(}$'s make the expression unclear and therefore harder to process. So the $\color{blue}{[}$'s are used.

Or if you really prefer the round parentheses you can just make them larger:

$$\bigg(5-\Big(6-7(2-6)+2\Big)\bigg)+4=5-(6+28+2)+4=5-36+4=-27$$ Start by computing the inner-most (smallest) bracket and work your way outwards.

The other context apart from intervals as you mentioned in your post; like for some $x$ $$[0,1]\implies 0\le x \le 1$$ is that the square brackets are used to return the dimensionality of some formula eg. \begin{align}[\text{Speed}]=\mathrm{ms}^{-1}\ & =\quad\text{meters per second}\end{align}

Here square brackets means parentheses but not interval. While solving these type of questions first solve the expression in ( ) next solve the expression in flower bracket i.e. { } next sole the expression on square brackets i.e. [ ]. Please don't take [.] as greatest integer function. In this problem we must start computing from inner most bracket to outwards. $$[5-(6-7(2-6)+2)]+4$$ $$=[5-(6+28+2)]+4$$ $$=[5-36]+4$$ $$=-31+4$$ $$=-27$$

$$[5-(6-7(-4)+2)]+4 \implies [5-(6+28+2)] + 4 \implies [5-36] +4 \implies -27$$

• If your "->" means "equals", then you should just write "$=$". Feb 21, 2016 at 8:42


text:
# Degree of extension to the splitting field - where's the mistake?

I have this false prove which I can't find the problem in. Trying to find the field extension degree $[E:\mathbb{Q}]$ where $E$ is the splitting field of the polynomial $f(x)=x^3-5$ over $\mathbb{Q}$.

My false proof is: The roots of $f$ in E are $a,b,c$, we don't need to state them precisely at the moment. Since $f$ is irreducible over $\mathbb{Q}$, $f(x)=irr(a,\mathbb{Q})=irr(b,\mathbb{Q})=irr(c,\mathbb{Q})$, and hence $\mathbb{Q}/(x^3-5) \cong \mathbb{Q}(a) \cong \mathbb{Q}(b) \cong \mathbb{Q}(c)$, therefore $b,c\in \mathbb{Q}(a)$, therefore $E=\mathbb{Q}(a,b,c)=\mathbb{Q}(a)$, therefore $[E:\mathbb{Q}]=3$.

This contradicts several other things, which are the reason I believe this prove is false. Can you spot the not?

Thanks, G.

-
btw, when writing a post, how do I start a new line without making an empty line in between? when I just press "enter" it stays in the same line... :) –  cruvadom Jan 26 '13 at 16:20
I don't know exactly what your typesetting complaint is. Either you start a new paragraph (with a blank line in the input) which is displayed with a bit of vertical whitespace (given that paragraphs have no indentation on their first line, they would be hard to recognise without this whitespace), or you don't start a new paragraph and then you get nothing in the output (but you can make your input start a new line for your personal convenience). –  Marc van Leeuwen Jan 26 '13 at 16:25
"but you can make your input start a new line for your personal convenience" how do I do that? –  cruvadom Jan 26 '13 at 16:29
You already know how to do that, you started "The roots", "Since" and "G." on fresh lines, and it still shows in the input (what you see when you het "edit"). I think you are asking the same for the output (visible to everyone), but you can't get that without vertical whitespace. –  Marc van Leeuwen Jan 26 '13 at 16:43

The error is in "$\mathbb{Q}(a) \cong \mathbb{Q}(b) \cong \mathbb{Q}(c)$ therefore $b,c\in \mathbb{Q}(a)$". The three fields you list are isomorphic but distinct subfields of $E$, which has degree $6$ over $\Bbb Q$. Indeed one can see that $\frac ab,\frac bc, \frac ac$ are all roots of $X^2+X+1$, which is an irreducible quadratic polynomial over $\Bbb Q$, whence neither of these roots can lie in any of the degree $3$ extensions listed, so each of those extensions can contain only one of $a,b,c$.

-
same comment as below - just because I believe you might also have something interesting to say about it: consider this example: the splitting field of $x^2+x+1$ over $\mathbb{Q}$. there are two complex roots "$a$" and "$b$"$=a^2$, and the splitting field $E=\mathbb{Q}(a)=\mathbb{Q}(b)$. so this situation can happen. –  cruvadom Jan 26 '13 at 16:59
@cruvadom: Yes, in general a field that contains one root of a quadratic polynomial contains them all. This is specific for degree $2$ though, and somehow related to the identity $2!=2$. Or to the following truism: if a polynomial in $K[X]$ of degree $d>0$ is divisible by a product of $d-1$ factors of degree $1$ in $K[X]$, then it can actually be written as a product of $d$ factors of degree $1$ in $K[X]$ (applied for $d=2$). –  Marc van Leeuwen Jan 26 '13 at 17:41

As others said, your mistake is to assume that isomorphism of fields implies equality. To make this absolutely clear consider the following. Exactly one of the roots of $x^3-5$ is real. Therefore exactly one of those three fields consists of real numbers only - the other two do not. Hence they cannot be equal (even though they are isomorphic).

-
consider this example: the splitting field of $x^2+x+1$ over $\mathbb{Q}$. there are two complex roots "$a$" and "$b$"$=a^2$, and the splitting field $E=\mathbb{Q}(a)=\mathbb{Q}(b)$. so this situation can happen. –  cruvadom Jan 26 '13 at 16:56
@cruvadom: Correct, but there the equation $$x^2+x+1=(x-a)(x-b)=$$ dictates a relation $a+b=1$ (in addition to the $b=a^2$ that you mentioned). And the field equality $\mathbb{Q}(a)=\mathbb{Q}(b)$ is a consequence of these. When the irreducible polynomial has three roots, this may or may not happen. It did not happen with the polynomial in your OP. But it does happen e.g. with the polynomial $$(x-2\cos\frac{2\pi}7)(x-2\cos\frac{4\pi}7)(x-2\cos\frac{8\pi}7)=x^3+x^2-2x+1$$(unless I made a mistake), because $\cos 2\alpha=2\cos^2\alpha-1$ is polynomially related with $\cos\alpha$. –  Jyrki Lahtonen Jan 26 '13 at 20:18
Your error is with the misunderstanding of what an isomorphism is and what it does. The two groups $\mathbb{Z}/2\mathbb{Z}$ and the group of permutations of $\{1,2\}$ are isomorphic but they have completely different elements (one consists of classes of integers, the other permutations).
Thanks, I sure know the difference between equality and isomorphism. my misconception was that the equivalent of $b$ under the isomorphism, lies somewhere inside $\mathbb{Q}(a)$ –  cruvadom Jan 26 '13 at 16:43
Yes, so $b$ doesn't necessarily lie in $\mathbb{Q}(a)$ since isomorphism isn't equality. –  fretty Jan 27 '13 at 19:15


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 14 Dec 2018, 07:11

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

## Events & Promotions

###### Events & Promotions in December
PrevNext
SuMoTuWeThFrSa
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345
Open Detailed Calendar
• ### GMATbuster's Weekly GMAT Quant Quiz, Tomorrow, Saturday at 9 AM PST

December 14, 2018

December 14, 2018

09:00 AM PST

10:00 AM PST

10 Questions will be posted on the forum and we will post a reply in this Topic with a link to each question. There are prizes for the winners.
• ### Typical Day of a UCLA MBA Student - Recording of Webinar with UCLA Adcom and Student

December 14, 2018

December 14, 2018

10:00 PM PST

11:00 PM PST

Carolyn and Brett - nicely explained what is the typical day of a UCLA student. I am posting below recording of the webinar for those who could't attend this session.

# If c is the product of a and b, which of the following is the quotient

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 51215
If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 04:59
00:00

Difficulty:

15% (low)

Question Stats:

78% (01:15) correct 22% (01:41) wrong based on 55 sessions

### HideShow timer Statistics

If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

_________________
Director
Status: Learning stage
Joined: 01 Oct 2017
Posts: 931
WE: Supply Chain Management (Energy and Utilities)
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 05:21
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

Hi Bunuel,
I couldn't figure out "what is quotient of a and b". I know "quotient concept is related to a division operation. Is it "which of the following is quotient of a/b"?
_________________

Regards,

PKN

Rise above the storm, you will find the sunshine

Math Expert
Joined: 02 Aug 2009
Posts: 7106
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 05:30
2
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

The question must be meaning quotient when a is divided by b..
See the choices..

A) $$\frac{b^2}{c}$$....$$b^2/c * b=b^3/c=b^2/a$$

B) $$\frac{c}{b^2}$$.......$$c/b^2*b=c/b=a$$..answer

B
_________________

1) Absolute modulus : http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
2)Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html
3) effects of arithmetic operations : https://gmatclub.com/forum/effects-of-arithmetic-operations-on-fractions-269413.html

GMAT online Tutor

Senior SC Moderator
Joined: 22 May 2016
Posts: 2207
If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 19:25
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

"The quotient of $$a$$ and $$b$$" means "$$a$$ divided by $$b$$." In English, if the operation is division, the quantity mentioned first goes on top.

I. Algebra
Answers have only $$b$$ and $$c$$

Define $$a$$ in terms of $$b$$ and $$c$$

1) $$a*b=c$$

2) $$a=\frac{c}{b}$$

3) $$\frac{a}{b}= ?$$

Substitute $$a$$'s value from (2) above ($$\frac{c}{b}$$) into $$\frac{a}{b}$$

$$\frac{a}{b}= \frac{(\frac{c}{b})}{b} = \frac{c}{b^2}$$

II. Assign values
Almost always, if VICs and division are involved, assign values that are ALL even, and make dividend greater than divisor. Use unusual numbers, but not too hard.*
$$(a*b)=c$$
Let
$$a=10$$
$$b=2$$, so
$$c=20$$

$$(a*b)=c$$
$$(10*2)=20$$, and
$$\frac{a}{b}=\frac{10}{2}=5$$

Using $$b=2$$ and $$c=20$$, find the answer choice that yields $$5$$

A) $$\frac{b^2}{c}=\frac{4}{20}=\frac{1}{5}$$ REJECT

B) $$\frac{c}{b^2}=\frac{20}{4}=5$$ KEEP

C) $$\frac{b}{c^2}=\frac{2}{(20)(20)}$$ = tiny. REJECT

D) $$bc^2=(2*20*20)$$ = huge. REJECT

E) $$b^2c=(2*2*20)$$ = huge. REJECT

*"Usual" = 0, 1, and 2. If you pick (2 * 1) = 2, answers B and E will be correct. Or usual = only multiples of 2 such as 4, 2, 8. They work here, but often, they will yield more than one correct answer.
Director
Status: Learning stage
Joined: 01 Oct 2017
Posts: 931
WE: Supply Chain Management (Energy and Utilities)
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 22:19
PKN wrote:
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

Hi Bunuel,
I couldn't figure out "what is quotient of a and b". I know "quotient concept is related to a division operation. Is it "which of the following is quotient of a/b"?

Hi Bunuel,
My doubt is cleared. Thanks to Quant mega-thread.

In the following cases, order is important:
‘quotient/ratio of’ construction
If a problems says ‘the ratio of x and y’, it means ‘x divided by y’ NOT 'y divided by x'.

Thanks generis for elaborating it. Your last line may be a typo(Ans. (C))
_________________

Regards,

PKN

Rise above the storm, you will find the sunshine

Senior SC Moderator
Joined: 22 May 2016
Posts: 2207
If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

17 Aug 2018, 22:45
PKN wrote:

generis Your last line may be a typo(Ans. (C))

PKN , thank you! Indeed it is a typo. Maybe now my pals on the verbal forums will believe me when I say that I never edit my own work!
VP
Joined: 07 Dec 2014
Posts: 1128
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

18 Aug 2018, 06:30
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

ab=c
dividing by b, a=c/b
dividing by b again, a/b=c/b^2
B
Intern
Joined: 25 Jul 2012
Posts: 28
Location: India
Concentration: Finance, Marketing
GMAT 1: 660 Q44 V37
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

18 Aug 2018, 06:36
c=a*b
Thus, a = c/b
We need to find a/b
therefore, (c/b)/b
Thus, a= c/b^2
_________________

If you like my post, consider giving me KUDOS

Target Test Prep Representative
Affiliations: Target Test Prep
Joined: 04 Mar 2011
Posts: 2830
Re: If c is the product of a and b, which of the following is the quotient  [#permalink]

### Show Tags

20 Aug 2018, 10:33
Bunuel wrote:
If c is the product of a and b, which of the following is the quotient of a and b?

A) $$\frac{b^2}{c}$$

B) $$\frac{c}{b^2}$$

C) $$\frac{b}{c^2}$$

D) $$bc^2$$

E) $$b^2c$$

We are given that c = ab. We need to find a/b in terms of b and c as we can see from the given choices. We can multiply a/b by b/b and obtain:

a/b * b/b = ab/b^2 = c/b^2

Alternate Solution:

We know that ab = c. Dividing each side of the equation by b^2, we get a/b = c/b^2.

_________________

Jeffery Miller

GMAT Quant Self-Study Course
500+ lessons 3000+ practice problems 800+ HD solutions

Re: If c is the product of a and b, which of the following is the quotient &nbs [#permalink] 20 Aug 2018, 10:33
Display posts from previous: Sort by


text:
# NIELIT 2016 MAR Scientist D: 20

1 vote
74 views

The question is based on the information given below:

As Sumit closes his eyes to go to sleep, he visualizes nine sheep jumping over a fence. The sheep’s names are Arti, Bhola, Chotu, Dhuli, Esha, Fallu, Golu, Heera, an Itti. The sheep are either in the pasture or outside of the pasture based on whether or not they have jumped over the fence. Their presence is governed by the following constraints:

1. If Golu is in the pasture, then Dhuli is out.
2. If Fallu is in the pasture, then Arti is out.
3. Itti is in the pasture if Fallu is out.
4. Dhuli is in the pasture if Chotu is in.
5. Esha is in the pasture if Bhola is out.
6. Heera is outside of the pasture.
7. If Golu is outside of the pasture, then Esha is out.

Which of the following pairs can never be in the pasture at the same time?

1. Fallu, Itti
2. Esha, Bhola
3. Dhuli, Chotu
4. Chotu, Esha

recategorized

The answer is (D). Chotu, Esha

618 points 1 9

## Related questions

1
228 views
The question is based on the information provided below: Eight fighter pilots flying over a conflict region notice some hostile activity taking place in a village. To peaceably resolve the conflict, they land their planes and decide that it would be best to send those pilots who would best complement each other as negotiators to ... $\text{G, D, C}$ $\text{E, A, H, F}$ $\text{A, B, F, G}$
2
218 views
The question is based on the information provided below: Eight fighter pilots flying over a conflict region notice some hostile activity taking place in a village. To peaceably resolve the conflict, they land their planes and decide that it would be best to send those pilots who would best ... not chosen. Who could be sent to negotiate alone? $\text{G}$ $\text{A}$ $\text{C}$ None of the above
3
157 views
The question is based on the information provided below: Eight fighter pilots flying over a conflict region notice some hostile activity taking place in a village. To peaceably resolve the conflict, they land their planes and decide that it would be best to send those pilots who would best ... $5$ $6$ $7$ $8$
4
213 views
The question is based on the information provided below: Eight fighter pilots flying over a conflict region notice some hostile activity taking place in a village. To peaceably resolve the conflict, they land their planes and decide that it would be best to send those pilots who would best complement each other as negotiators to ... $\text{H, B, A, C, D}$ $\text{H. C, D, B, A, F}$
The question is based on the information provided below: Eight fighter pilots flying over a conflict region notice some hostile activity taking place in a village. To peaceably resolve the conflict, they land their planes and decide that it would be best to send those pilots who would ... negotiate $\text{E}$ is sent to negotiate $\text{B}$ is sent to negotiate $\text{G}$ is sent to negotiate


text:
# Tag Info

17

Brief answer: Read only the bold part (and ignore grammar then). The answer you already mentioned lies in Quantum Field Theory (QFT). But to fully understand it, you must give up a particle as a point-like thing that is well-localized. There is one Quantum Field per sort of particle, e.g. the electron field for all electrons, and the photon field for all ...

14

Let me give a second, more technical answer. Observable particles. In QFT, observable (hence real) particles of mass $m$ are conventionally defined as being associated with poles of the S-matrix at energy $E=mc^2$ in the rest frame of the system (Peskin/Schroeder, An introduction to QFT, p.236). If the pole is at a real energy, the mass is real and the ...

14

The short answer for why gravity is unique is that it is the theory of a massless, spin-2 field. To contrast with the other forces, the strong, weak and electromagnetic forces are all theories of spin-1 particles. Although it's not immediately obvious, this property alone basically fixes all of the essential features of gravity. To begin with, the fact ...

8

For example, how do two charged particles know that they are to move apart from each other? Do they communicate with each other somehow through some means? Yes, specifically the electromagnetic field. To give a simplistic view, a charged particle produces an electric field to indicate its presence and a magnetic field to indicate its motion. Any ...

6

When you ask "Why is gravity such a unique force?" then you should know that in the framework of General Relativity gravity is not a force at all. In General Relativity energy (for example the mass of an object) cause curvature. The movement of other objects is influenced by this curvature - they travel along the path of shortest distance between two points ...

6

Photons are force carrying bosons and come in both virtual and real varieties. There is nothing wrong with that. Virtual means off-shell, and real means on-shell. Even on-shell weak bosons decay very quickly, however, because there are plenty of modes with the right quantum numbers and much lower total mass (and thus lots of phase space). I want to ...

5

The short answer in quantum field theories is "by the exchange of virtual particles". Look up "virtual particles" on Wikipedia to get a sense of it. The ancillary questions you asked about the energy budget, and the derivation of Coulomb's law are very much the right ones. They should all be answered there. For example, energy is conserved except for ...

4

You say: Gravity depends on mass but this is not so. The source of the gravitational field is an object called the stress-energy tensor. One element of this object is the energy density, and mass contributes to this through Einstein's well known equation $E = mc^2$, but mass is not required to generate a gravitational field. Even massless particles ...

4

All observed particles are real particles in the sense that, unlike virtual particles, their properties are verifiable by experiment. In particular, W and Z bosons are real but unstable particles at energies above the energy equivalent of their rest mass. They also arise as unobservable virtual particles in scattering processing exchanging a W or Z boson, ...

2

The notion of a point-like but charged particle is somewhat contradictory: on one hand we imagine it as localized in space (like a neutral particle); on the other hand, such a "particle" is "long-handed", i.e., it is felt far away from it "position". One may think that the charge is not point-like but is a "part" of a complicated, extended system. When you ...

2

Hello and welcome to the cite. Yes -- the carrier for any electromagnetic interaction is a photon. Including ordinary magnets. You might ask: "Why then can't I see those photons?" Well, even from classical point view, the photons can have different wavelenghts. And with the magnet you deal with really large wavelenghts, while one cannot "see" radiowaves. ...

2

One could write a novel about those questions... I'll try to nail down the most important facts. Regarding what you figured out so far: Basically correct. I would say: Every system of atoms has a quantum mechanical ground state. You can approximately assign an energy to each of the electrons (depending on the approximation you are using, e.g. Hartree-Fock ...

2

They can be real, no problem with that. However, all Z and W observed are virtual. And yes, they are off-shell, whatever that means to you. We actually measure their width, for instance, http://arxiv.org/pdf/0909.4814 (it's more or less 2 GeV around a mass of more or less 80-90 GeV). What is observed is a pole in the S matrix for some final states in ...

1

I think you can get a estimate like this. For a semiconductor with no split in the quasi-Fermi levels, the electrons and holes take their intrinsic values (carrier density) $n_0$ and $p_0$ ($cm^{-3}$). The charge carriers are in equilibrium with the thermal photons being absorbed and emitted inside the material. So if we calculate the emission rate of ...

1

the injection level is defined as $\delta n/p_0$ where $\delta n$ is the minority carrier (e.g. electrons') density excess at non-equilibrium while $p_0$ is the equilibrium density of the majority carriers (e.g. holes). From the formula which is a ratio of two very similar densities, it's clear that the injection level is dimensionless; "high" and "low" ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Tag Info

40

The initial and final permutation have no influence on security (they are unkeyed and can be undone by anybody). The usual explanation is that they make implementation easier in some contexts, namely a hardware circuit which receives data over a 8-bit bus: it can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit ...

11

In theory. No. The inverse of a secure PRP need not be a secure PRP. Here is what we can guarantee. The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP. Any secure sPRP is a secure PRP. Therefore, the inverse of a secure sPRP will be a secure PRP. FYI, if you are not familiar with PRP/sPRP, the difference ...

8

The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input ...

8

First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's. Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself. Now, permutations on a finite ...

7

Yes, an additional bit permutation of pseudo-random data from a secure Pseudo-Random Number Generator is secure, subject to the condition that this bit permutation is independent of the key material of the PRNG and of any data derived from that (including the pseudo-random data). An argument is that if this permutation is public, the adversary can do/undo ...

6

a permutation will rearrange the input producing something of arbitrary length. I'm not sure about this. My understanding of a permutation is that it will always produce an output of the same length as the input. That is, a permutation simply reorders all the parts of the input without adding or removing any elements. A hash function does not have ...

6

There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$. It is evident that AES is not a uniformly chosen permutation, since its permutation is fixed for any key. One can consider a family $\{AES_K\}$ of AES permutations under all possible keys $K$. Even if the key is chosen ...

6

As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output. In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if: no two inputs are mapped to the same ...

5

If I understand correctly, you want a function that for each input string $p$ assigns a permutation over an alphabet $L$. If the number of elements in $L$ is small enough, the permutation set $P(L)$ will be enumerable. More precisely, $|P(L)| = |L|!$. There exists a surjective function $f:\{0,1\}^k \to P(L)$ that for each bit string $s$ of length $k$ ...

5

Our Professor, Christof Paar, sat together on lunch a few years ago with one of the main designers of DES. He said that for getting it as specification, they had to build a piece of hardware which encrypts via DES. Shortly before finishing the project, they discovered that their wiring into the box was somewhat intermingled. Building such hardware stuff was ...

4

Something I wrote years ago to describe the IP and Inverse IP. With a copy of the FIPS Pub in hand you can see the correlation between registers and bits. Essentially the data is shifted in serially (for an interface smaller than 64 bits, in this case 8 bits wide) and used in a parallel fashion. In hardware and an 8 bit interface the IP and Inverse IP ...

4

In Algebra, a Permutation of a set $X$ is a bijective function $\sigma:X{\rightarrow}X$ that for each element $x \in X$ assigns a unique value $\sigma(x) \in X$. In practice, this could mean a lot of things. For instance, in DES a permutation is used that rearranges the position of the bits of the half block. This is a permutation ...

4

I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure. For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size ...

4

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means? You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set. Basically, this map is a permutation if ...

4

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$. It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements). It holds that ...

4

The permutations in your question are given in Cauchy's two-line notation, where the upper line gives the input index to the permutation function, and the lower line gives the resulting permuted index. For example, the definition $$\sigma = {1\ 2\ 3 \choose 3\ 1\ 2}$$ means the same as $$\sigma(1) = 3,\quad \sigma(2) = 1,\quad \sigma(3) = 2.$$ Thus, if we ...

4

In the substitution step of a typical Substitution-Permutation Network (e.g. in AES SubBytes), the whole state is broken in parts and each part substituted. That's not the case in (the core of) a Feistel cipher, where at each step/round some sizable part of the state is bound to remain unchanged (in order that each step be reversible).

4

If you can generate uniform random numbers, you can use a variant of Fisher-Yates. //given an array s with the elements to be permuted for i from n-1 to 1: t = rand(0, i) # inclusive swap(s[i], s[t])

3

In a strict sense, no. NP is about worst-case hardness. Cryptography requires average-case hardness. $P \ne NP$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness. For block ciphers, we need average-case hardness. Therefore, there are good ...

3

At some level, there is no essential difference. Certainly, there is no difference in the distribution on the random variable $O$ vs $f$. However, there is a potential difference in how the terms are typically used. If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate ...

3

If you take a pseudo random permutation permutation you usually get a hard to invert PRF. AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough. Commonly used compression functions are built from block-ciphers with similar techniques: For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses: $H_i ... 3 There are so many possible solutions here. Without giving your requirements more carefully, it's just not possible to tell what would count as a valid solution. Here are a bunch of schemes that offer better security than simply truncating to$N/2$bits and applying 4 rounds of Luby-Rackoff: For instance, one approach is to truncate the random function to ... 3 permutation is mapping a finite set to itself (a bijection from Set to itself) hash function is not a permutation, because it has tow different sets: input: infinite variable length output: finite fixed length 3 How secure is this cipher? At first glance, not very. It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no ... 3 Yes, it is possible to implement the primitive asked, with a 32-bit block cipher that is secure (indistinguishable from a random permutation) no matter how many input-output pairs are known, keyed with a fixed secret randomly-chosen key. That's a standard building block in Format Preserving Encryption. One such block cipher is: Louis Granboulan and Thomas ... 3 Assuming that the probability distributions of$\pi_{k_1}$and$\pi_{k_2}$are both uniform (that is, each permutation can take on any particular setting with probability$1/n!$), then no, adversary does not have enough information to learn anything about the original positions. This remains true even if we assume the adversary can perform unbounded ... 2 For Vigenère specifically, you can make it harder to break by increasing the size of the key and by making the key truly random. If the key is truly random, longer than the plaintext and never reused, then Vigenère becomes equivalent to a One Time Pad. Even without going that far, it is possible to strengthen many, though not all, cyphers by lengthening ... 2 All permutations have a cycle decomposition from which you may immediately read off your$P(n-2)$and$P(n-1)$. There are trivial algorithms for doing this that run in either$O(n)$time and$O(n)$space (invert the permutation), or$O(n^2)$time and$O(1)$space (walk backwards by querying everybody repeatedly). You could adapt that invert the permutation ... 2 Sticking to monoalphabetic ciphers, Vigenere can be combined with a secret random-like substitution of the plaintext or/and ciphertext alphabet, making it significantly more resistant. If Vigenere encryption is $$x_j\mapsto (x_j+K[j\bmod k])\bmod{26}$$ where array$K$is the key or length$k$, I'm discussing $$x_j\mapsto (S[x_j]+K[j\bmod k])\bmod{26}$$ ... 2 If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this: A block cipher, together with a key$k$($|k|$=$M\$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Is it true that $U \cap (W_1 \oplus W_2) = (U \cap W_1) \oplus (U \cap W_2)$?

Let $$W_i (i =1,2)$$ be subspaces of $$V$$. $$W_1 \cap W_2 =0$$. If $$U$$ is a subspace of $$V$$, is it true that $$U \cap (W_1 \oplus W_2) = (U \cap W_1) \oplus (U \cap W_2)$$?

If it is true, is there any way to give a formal proof? If it is not, is there a hint for constrcting a contradiction or giving a counter example?

• No, it is not true. – Charlie Frohman Jul 31 at 23:13

It is false. Take $$V=\mathbb R^2$$, $$W_1=\mathbb R\times\{0\}$$, $$W_2=\{0\}\times\mathbb R$$, and $$U=\{(x,x)\mid x\in\mathbb R\}$$. Then $$U\cap W_1=U\cap W_2=\{0\}$$, but $$U\cap(W_1\bigoplus W_2)=U\neq\{0\}$$.

• So this counterexample can be considered as a $y=x$ linear on a $x-y$ plane where $W_1$ is x-axis and $W_2$ is y-axis? – WaterBro Jul 31 at 23:16
• That's a way of looking at it, yes. – José Carlos Santos Jul 31 at 23:18


text:
# B Distinguishing inertial reference frames

1. Mar 22, 2016

### bwana

As described in Wikipedia as well as this entry http://physics.stackexchange.com/qu...xplanation-of-the-equivalence-principle-wrong,
"being at rest on the surface of the Earth is equivalent to being inside a spaceship (far from any sources of gravity) that is being accelerated by its engines." Even more fundamentally, in an elevator in space, how do you know you are moving at a constant speed or are stationary?

I am confused about something. Consider the following situation:

An alien with spectacular vision (that can resolve time differences on the order of 10^-12 seconds) is in a train that is stationary and is looking at a light that is very briefly pulsed on-off about a meter away from his eye. The light is pulsed at time t1 and he perceives it at t2.( even though it has been off for a long time by then). Now consider the situation when the train starts to move.

The alien sees the same event. There are no windows and there is no way the alien can get information from outside the cabin. According to the fact that the train is not accelerating but moving at a constant velocity, nothing the alien can do should tell him that he is moving. But consider which photons the alien is seeing.

When the light is pulsed, the photons go in all directions. In a stationary train, the alien sees the photon going straight up, but in the moving train, the photon that reaches his eye, is the one that takes off from the light at an angle.

Now make a stencil with numbers cut out on it like so:

and put it right over the light like so:

Please forgive the scale. I wanted to make the numbers readable so I made the mask very large. You might be tempted to say that by the time the light pulse traveling obliquely reaches the mask, the mask will have moved so the alien will really see a different number (2 maybe?). But make the mask really small so it is really close to the source. And make the stenciling really small so you can resolve small differences.

When the train is stationary, the alien sees the number '1' but when the train is moving he sees the number '5'. Again, remember, the mask is really, really close to the light source. If the mask were really big the way I drew it (for clarity) then the alien would always see the number '1'.

So it seems to me that such a 'light speedometer' can tell us how fast our frame of reference is moving even without any information from outside our frame. It relies on the fact that we know the speed of light is constant in all inertial reference frames. This seems to suggest that we can distinguish inertial frames of reference. It goes all the back to the idea of Newton who spoke about absolute reference frames here
http://plato.stanford.edu/entries/spacetime-iframes/

Please note, I have not made any claims about time or the concept of simultaneity. I am not discussing special relativity. Yet the concept of the space elevator introduced by Einstein now bothers me. With such a 'light speedometer' shouldn't I be able to know how fast I am going in an absolute sense?

2. Mar 22, 2016

### DrGreg

See this from an old post of mine:
[PLAIN]https://www.physicsforums.com/attachments/bounce-in-a-moving-train-gif.80718/[QUOTE="DrGreg, [Broken] post: 5048516, member: 35885"] Here's something (it could be a pulse of light, it could be a ball) bouncing up and down in a train.

An observer in the train (top) infers the thing is moving vertically up and down.

An observer on the ground (bottom) infers the thing is "sliding sideways" in a zig-zag path.

This is valid in both relativistic and Newtonian mechanics.[/QUOTE]

Last edited by a moderator: May 7, 2017
3. Mar 22, 2016

### Staff: Mentor

If he sees a 1 when the train is stationary, then he sees a 1 when the train is moving inertially. The size of the mask doesn't make any difference.

4. Mar 22, 2016

### bwana

@ Dale The alien CANNOT see a 1 because the photons from the light pulse that carry the '1' information are going straight up. By the time those few photons reach where his head should be, his head has moved on. The photons that strike his eye at t2 are not carrying '1' information. The only photons that reach his eye at t2 are traveling obliquely. All photons intercept the mask early in their travel so the oblique ones carry '5' information. This is because at the very beginning at t1, vertical photons are labeled 1 and oblique photons are labeled 5. For simplicity, I postulated a very brief light pulse at t1. When the '1' mask is under his eye at t2, there is no light. The train is not going at the speed of light.

@greg I am NOT considering what anyone sees outside the train. The mask, the light and the alien are ALL in the train. Your drawing attempts to illustrate relativity between two different reference frames - one stationary and one moving. I am only looking at what is going on inside the train.

Last edited: Mar 23, 2016
5. Mar 23, 2016

### Orodruin

Staff Emeritus
You are (wrongly) assuming that the scale is not moving. It will go through one because the scale (and therefore the one) moves with the train. If the scale does not move with the train, it will not go through 1, bit the alien will attribute this to the scale moving relative to him so it is no longer the same experiment.

This is nothing but abberation of light - it travels in different directions in different frames. You can obsreve abberation when you drive on a rainy day - all the rain seems to be coming from the front, but in the Earth rest frame it goes straight down.

6. Mar 23, 2016

### Ibix

@bwana - DrGreg's answer is correct. Your last diagram is wrong. It shows (viewed from an inertial frame in which the train is moving to the right) where the alien is at the time of the emission and where it is at the time it sees the pulse. But it only shows the stencil at the time of emission, not at the time the pulse passes it. If the number 1 is a fraction $f$ of the height of the train above the source, the travel time of the light is $\Delta t$, and the horizontal travel of the alien in that time is $\Delta x$ then the light pulse will be at the same height as the 1 at time $f\Delta t$, at which point the 1 will have moved horizontally $f\Delta x$. In other words - right on your diagonal ray.

You can't get out of this by making $f$ small, which is what I think you are trying to do. You can only avoid it by making $f=0$, in which case all the numbers are in the same place and the ray goes through all of them.

7. Mar 23, 2016

### Staff: Mentor

You seem to forget that the mask is travelling at the same speed too. If he sees a 1 at rest then he sees a 1 at any uniform velocity. The 1 selects obliquely moving light when it is moving. You should work out the math on this.

The size of the mask and it's distance to the source are not relevant.

Last edited: Mar 23, 2016
8. Mar 23, 2016

### DrGreg

Just look at my top diagram and ignore the pale blue gridlines and the pink diagonal line. The red ball is moving vertically up and down, i.e. in the "1" direction of the stencil attached to the train. There's a vertical U-shaped black "tube" on the floor of the train that is effectively the same thing as your stencil.

If you had another stencil attached to the ground, the bottom diagram shows how the ball would be measured by that second stencil in the "5" direction.

9. Mar 23, 2016

### pixel

10. Mar 24, 2016

### bwana

Thank you. That was helpful and I apologize for recapitulating an already explained topic. Specifically, this sentence

'The same applies to photons, which have impulse just like the ball'

I also appreciate the time everyone took to answer. I know I did not use fancy math but it was the underlying model of light on which the fancy math is based.

11. Mar 24, 2016

### Staff: Mentor

But you didn't use the underlying model on which the math is based. If you had then you would have gotten an answer which agreed with the math.

Do you feel that you have now adjusted your mental model to understand how the "1" selects obliquely moving light?

12. Mar 24, 2016

### bwana

Indeed. Photons behave just like billiard balls. The only difference is that we do not have any tool that travels faster than they do. As a result we need to use relativistic corrections when studying them from different reference frames.

13. Mar 24, 2016

### Orodruin

Staff Emeritus
They most certainly do not. They behave as excitations of quantum fields. If you do not feel comfortable with that you should probably refer to "light pulses" instead of photons.


text:
# inaccuracy in Schilling Proposition 6.5

I found an inaccuracy in the Proposition 6.5 of the book "Measures, Integrals and Martingales" From René Schilling [EDIT: I'm talking about the first edition of the book] and I would like to correct this error.

To be sure that I'm clear in asking the question I will list the definitions I use in this post so that there are no notational misunderstandings.

I will try to make sure that even those unfamiliar with the book can answer the question. But obviously those who have studied from that book are more likely to be able to answer the question.

I organized this post in the following way:

In the first part there's the question.

In the second part there is the list of definitions and notations that I use, so if you come across a symbol or a definition that you do not know go to read the second part.

In the third part there is the reason that led me to formulate the question, how the question is related to proposition 6.5 and what was my attempt to answer the question.

FIRST PART: THE QUESTION

[Edit: as suggested I changed the name of the "Theorem 0.2" calling it "Statement 0.2"]

Statement 0.2: Let $$X$$ be a set, $$\mathcal F$$ a semi-ring on $$X$$ and $$\mu : \mathcal F \to [0,+\infty]$$ a function then

$$\mu$$ is a pre-measure on $$X$$ if and only if

[$$\begin{split} &(i) \hspace{0.5cm} \mu(\emptyset)=0 \\ &(ii) \hspace{0.5cm} A \in \mathcal F, B \in \mathcal F , A \cap B = \emptyset , A \cup B \in \mathcal F \implies \mu(A\cup B)=\mu (A) + \mu (B) \\ &(iii) \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_n \subseteq A_{n+1} \forall n \in \mathbb N , \bigcup_{n \in \mathbb N} A_n \in \mathcal F \implies \mu(\bigcup_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \end{split}$$]

Moreover, with the additional hypothesis that $$\mu (A) < + \infty \forall A \in \mathcal F$$, (iii) can be replaced by either of the following equivalent conditions:

[$$\begin{split} &(iii') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N , \bigcap_{n \in \mathbb N} A_n \in \mathcal F \implies \mu(\bigcap_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \\ &(iii'') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N , \bigcap_{n \in \mathbb N} A_n = \emptyset \implies \lim _{n \to +\infty} \mu (A_n) = 0 \end{split}$$]

End of the Statement 0.2

MY QUESTION IS: is Statement 0.2 True? And what is the proof of the implication "from the right to the left"? If this implication of Statement 0.2 is not true what is an example of a set $$X$$ with a semi-ring $$\mathcal F$$ and a function $$\mu$$ on $$\mathcal F$$ which satisfies properties (i), (ii), (iii'') of Statement 0.2 but such that $$\mu$$ is not a pre-measure on $$X$$ ?

I could only prove the implication "from the left to the right" of theorem 0.2 but i couldn't prove the viceversa. If you want to see a sketch of the proof of the implication i proved, you can find it in the third part of the post.

SECOND PART: Notations and definitions I use

if $$X$$ is a set and $$\mathcal F \subseteq \mathcal P (X)$$ then we define:

$$\mathcal F$$ is a ring on $$X$$ if and only if (by definition) [$$\begin{split} &1) \hspace{0.5cm} \emptyset \in \mathcal{F} \\ &2) \hspace{0.5cm} A,B \in \mathcal{F} \implies B \setminus A \in \mathcal{F} \\ &3) \hspace{0.5cm} A,B \in \mathcal{F} \implies A \cup B \in \mathcal{F} \end{split}$$]

$$\mathcal F$$ is a semiring on $$X$$ if and only if (by definition) [$$\begin{split} &1) \hspace{0.5cm} \emptyset \in \mathcal{F} \\ &2) \hspace{0.5cm} A,B \in \mathcal{F} \implies \exists A_1,A_2,\dots,A_n \in \mathcal{F} \text{ pairwise disjoint } : \,\; B \setminus A = \bigcup_{k=1}^{n}{A_k}\\ &3) \hspace{0.5cm} A,B \in \mathcal{F} \implies A \cap B \in \mathcal{F} \end{split}$$]

it is easy to prove that a ring on $$X$$ is also a semiring on $$X$$

If $$X$$ is a set, $$\mathcal F \subseteq \mathcal P (X) : \emptyset \in \mathcal F$$ and $$\mu : \mathcal F \to [0,+\infty]$$ then $$\mu$$ is a pre-measure on $$(X, \mathcal F )$$ [or simply on $$X$$] if and only if (by definition) [$$\begin{split} &1) \hspace{0.5cm}\mu(\emptyset) = 0 \\ &2) \hspace{0.5cm} A_1,A_2,\dots \in \mathcal{F} \text{ pairwise disjoint , } \bigcup_{n\in\mathbb{N}}{A_n} \in \mathcal{F} \implies \mu\bigg( \bigcup_{n \in \mathbb{N}}{A_n}\bigg) = \sum_{n=1}^{\infty}{\mu(A_n)}\\ \end{split}$$]

so basically a pre-measure is the same as a measure with the only differences that a pre-measure isn't necessarily defined on a $$\sigma$$-agebra and the $$\sigma$$-additivity holds only when the union of the sets is in the domain of the function.

Moreover $$\mathcal J ^n$$ is the set whose elements are the subset of $$\mathbb R ^n$$ in the form $$[a_1,b_1) \times ... \times [a_n,b_n)$$ where $$a_i,b_i \in \mathbb R \forall i = 1,...,n$$

THIRD PART: Correlation of the question with proposition 6.5 and my attempt to answer the question

Now i will list some theorems of the Schilling required to understand the problem with proposition 6.5 and how it is related to Statement 0.2

Theorem 4.4: Let $$X$$ be a set, $$\mathcal F$$ a $$\sigma$$-algebra on $$X$$ and $$\mu : \mathcal F \to [0,+\infty]$$ a function then

$$\mu$$ is a measure on $$X$$ if and only if

[$$\begin{split} &(i) \hspace{0.5cm} \mu(\emptyset)=0 \\ &(ii) \hspace{0.5cm} A \in \mathcal F, B \in \mathcal F , A \cap B = \emptyset \implies \mu(A\cup B)=\mu (A) + \mu (B) \\ &(iii) \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N : A_n \subseteq A_{n+1} \forall n \in \mathbb N \implies \mu(\bigcup_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \end{split}$$]

Moreover, with the additional hypothesis that $$\mu (A) < + \infty \forall A \in \mathcal F$$, (iii) can be replaced by either of the following equivalent conditions:

[$$\begin{split} &(iii') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N \implies \mu(\bigcap_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \\ &(iii'') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N , \bigcap_{n \in \mathbb N} A_n = \emptyset \implies \lim _{n \to +\infty} \mu (A_n) = 0 \end{split}$$]

end of the Theorem 4.4

Then the book states that Theorem4.4 is still valid in a more general case, regarding pre-measures instead of measures. But, due to the fact that the proof of the Theorem 4.4 requires that the family $$\mathcal F$$ is closed under finite intersection, union and difference of sets, then this more general theorem is true in the hypotesis that $$\mathcal F$$ is a ring on $$X$$.

I could easily prove this more general theorem, I'll copy the statement below under the name of Theorem 0.1

Theorem 0.1 : Let $$X$$ be a set, $$\mathcal F$$ a Ring on $$X$$ and $$\mu : \mathcal F \to [0,+\infty]$$ a function then

$$\mu$$ is a pre-measure on $$X$$ if and only if

[$$\begin{split} &(i) \hspace{0.5cm} \mu(\emptyset)=0 \\ &(ii) \hspace{0.5cm} A \in \mathcal F, B \in \mathcal F , A \cap B = \emptyset \implies \mu(A\cup B)=\mu (A) + \mu (B) \\ &(iii) \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_n \subseteq A_{n+1} \forall n \in \mathbb N , \bigcup_{n \in \mathbb N} A_n \in \mathcal F \implies \mu(\bigcup_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \end{split}$$]

Moreover, with the additional hypothesis that $$\mu (A) < + \infty \forall A \in \mathcal F$$, (iii) can be replaced by either of the following equivalent conditions:

[$$\begin{split} &(iii') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N , \bigcap_{n \in \mathbb N} A_n \in \mathcal F \implies \mu(\bigcap_{n \in \mathbb N} A_n)=\lim _{n \to +\infty} \mu (A_n) \\ &(iii'') \hspace{0.5cm} A_n \in \mathcal F \forall n \in \mathbb N , A_{n+1} \subseteq A_n \forall n \in \mathbb N , \bigcap_{n \in \mathbb N} A_n = \emptyset \implies \lim _{n \to +\infty} \mu (A_n) = 0 \end{split}$$]

End of theorem 0.1

Now the problems begin.

The book defined the function $$\lambda ^n : \mathcal J ^n \to [0,+\infty)$$ that associates each element of $$\mathcal J ^n$$ to its volume.

The book also proved that $$\mathcal J ^n$$ is a semi-ring on $$\mathbb R^n$$ (Proposition 6.4)

My problem with the Proposition 6.5 is that the book wants to prove that $$\lambda ^n$$ is a pre-measure on $$\mathcal J ^n$$ using some sort of Theorem 0.1 but the problem is that $$\mathcal J ^n$$ is not a Ring on $$\mathbb R^n$$ but only a semi-ring.

Let me be clearer, this is the proposition6.5 of the book:

Proposition 6.5: $$\lambda ^n$$ is a pre-measure on $$\mathcal J ^n$$

Proof:

the proof of the book consists in showing that the properties (i) (ii) (iii'') of the theorem 0.1 holds for $$\lambda ^n$$ and i'm ok with this proof (obviously you need to modify the property (ii) requiring that $$A \cup B \in \mathcal J ^n$$ ) but the problem is that then he uses a not well specified version of the theorem 0.1 to conclude that $$\lambda ^n$$ is a pre-measure on $$\mathbb R^n$$. But, again, you can't use theorem0.1 because $$\mathcal J ^n$$ is not a Ring on $$\mathbb R^n$$ but only a semi-ring.

What was my attempt to solve this issue?

Firstly I have formulated a version of the theorem suitable for semi-rings which goes under the name of Statement 0.2 (You've read it in the first part of the post)

I will shortly show how i proved the first implication of the Statement 0.2 (The implication "from the left to the right"):

First of all I proved the following theorems:

Theorem 0.3 : Let $$X$$ be a set and $$\mathcal F \subseteq \mathcal P (X)$$ then it does exist the smallest Ring on $$X$$ containing $$\mathcal F$$ and it's denoted with the simbol $$R(\mathcal F)$$

Theorem 0.4 : Let $$X$$ be a set and $$\mathcal F$$ a semi-ring on $$X$$ then $$R(\mathcal F)$$ is the set of all the finite disjoint unions of elements of $$\mathcal F$$

Theorem 0.5 : Let $$X$$ be a set and $$\mathcal F$$ a semi-ring on $$X$$ and $$\mu : \mathcal F \to [0,+\infty]$$ a pre-measure on $$X$$ then there exists and is unique an extension of $$\mu$$ to $$R(\mathcal F)$$ such that this extension is a pre-measure.

Proof of the implication from the left to the right of Statement 0.2:

if $$\mu$$ is a pre-measure on the semi-ring $$\mathcal F$$ then denoted the unique extension of $$\mu$$ to $$R(\mathcal F)$$ still with $$\mu$$ we get the assertion thanks to Theorem0.1

• I think this is the first edition because there's no edition specified Apr 28 at 19:58
• In the second edition Schilling proves that $\lambda^n$ is a premeasure by induction on $n$. He verifies the two basic conditions that define a premeasure. Apr 29 at 6:52
• @GabrielRomon Thanks, i saw that. But i would like to prove it in the way the book "proved" it in the first edition. I need to know if the theorem 0.2 it's true or false. Apr 29 at 8:37
• "is Theorem 0.2 True?" Is it really a theorem from the book, or just a statement you write down? If it is a theorem from the book, then it wouldn't be published at all if it is false. If it is your statement, then you should probably just call it a "statement. May 9 at 0:43
• I edited following your suggestion May 9 at 7:19

In R. L.Schilling. Measure, Integrals and Martingales, Cambridge, First Edition 2005, there is no explicit version of Theorem 0.2. as stated by the OP. This is also the case for the second edition. The main result that resembles the OP's Theorem 0.2 is Theorem 4.4 on page 24 (first edition) which is stated under the assumption that $$(X,\mathcal{F})$$ is a measurable space (i.e. $$\mathcal{F}$$ is a $$\sigma$$-algebra of subsets of $$X$$):

Theorem 4.4: Suppose $$(X,\mathcal{F})$$ is a measurable space. A map $$\mu:\mathcal{F}\rightarrow[0,\infty)$$ is a measure iff

• (i) $$\mu(\emptyset)=0$$,
• (ii) $$\mu(A\cup B)=\mu(A)+\mu(B)$$ for all $$A,B\in\mathcal{F}$$ with $$A\cap B=\emptyset$$,
• (iii) $$\mu\big(\bigcup_nA_n\big)=\lim_n\mu(A_n)$$ for all monotone nondecreasing sequence of set $$(A_n:n\in\mathbb{N})\subset\mathcal{F}$$.

In addition, if $$\mu(A)<\infty$$ for all $$A\in\mathcal{F}$$, then (iii) is equivalent to either of the follwing conditions:

• (iii)' $$\mu\big(\bigcap_nA_n\big)=\lim_n\mu(A_n)$$ for any monotone nonincreasing sequence of of sets $$(A_n:n\in\mathbb{N})\subset \mathcal{F}$$.
• (iii)'' $$\lim_n\mu(A_n)=0$$ for any monotone nonincreasing sequence of of sets $$(A_n:n\in\mathbb{N})\subset \mathcal{F}$$ such that $$\bigcap_nA_n=\emptyset$$.

The confusion of the OP, I believe, stems from a remark (op. cit. Remark 4.5, page 24 of first edition) in the book that states that Theorem 4.4 and its precursor Proposition 4.3 (which I don't state but only mention that it is related to necessary conditions concerning monotonicity and subaditivity properties of any measure $$\mu$$) are valid when $$\mu$$ is a premeasure on $$\mathcal{F}$$ where $$\mathcal{F}$$ is not a $$\sigma$$-algebra, with the obvious re-wordings. Here is the precise statement in the book:

Remark 4.5: With some obvious rewordings, P4.3 and T4.4 are still valid for pre-measures, i.e. for families $$\mathcal{F}$$ which are not $$\sigma$$-algebras. Of course, one has to make sure that $$\emptyset\in\mathcal{F}$$, and that $$\mathcal{F}$$ is stable under finite unions, intersections and differences of sets$$^1$$ (for P4.3) and, for T4.4, that increasing and decreasing sequences of the sets under consideration have their limits in $$\mathcal{F}$$. The proofs are literally the same.

The superscript $$^1$$ in the textbook makes it clear that author refers to the case where $$\mathcal{F}$$ is a ring. In such case, Theorem 0.2. as stated by the OP holds and is not complicated to prove.

Now, If we consider a semiring $$\mathcal{R}$$ on $$X$$ and $$\mu$$ is a premeasure (as defined in the OP) on $$\mathcal{R}$$, conditions (i)-(iii) still hold. This I state as a Theorem R:

Theorem R: Suppose $$\mathcal{R}$$ is a semi-ring on $$X$$. If $$\mu$$ is a premeasure on $$\mathcal{R}$$, then

• (i) $$\mu(\emptyset)=0$$,
• (ii) $$\mu(A\cup B)=\mu(A)+\mu(B)$$ for all $$A,B\in\mathcal{R}$$ with $$A\cap B=\emptyset$$ and such that $$A\cup B\in\mathcal{R}$$,
• (iii) $$\mu\big(\bigcup_nA_n\big)=\lim_n\mu(A_n)$$ for all monotone nondecreasing sequence of sets $$(A_n:n\in\mathbb{N})\subset\mathcal{R}$$ such that $$\bigcup_nA_n\in\mathcal{R}$$.
• (iv) $$\mu$$ is countably sub-additive on $$\mathcal{R}$$, that is $$\mu\big(\bigcup_nB_n\big)\leq\sum_n\mu(B_n)$$ for any sequence $$(B_n:n\in\mathbb{N})\subset\mathcal{R}$$ such that $$\bigcup_nB_n\in\mathcal{R}$$.

• Conditions (i), (ii) and (iv) in Theorem R are the minimal ingredients to extend $$\mu$$ to a $$\sigma$$-algebra that contains the semiring $$\mathcal{R}$$ -This is the Carathéodory extension theorem (op. cit. Theorem 6.1 page 37 on first edition). Once the extension is achieved, then the equivalence between (iii) and either (iii)' or (iii)'' under finiteness follows by virtue of Theorem 4.4.
• The proof of Carathéodory's extension theorem relies on the construction of an outer measure $$\mu^*$$ by exploiting the countably additivity of the premeasure $$\mu$$ (i.e., $$\sum_n\mu(A_n)=\mu\big(\bigcup_nA_n\big)$$ for any sequence $$(A_n:n\in\mathbb{N})\subset\mathcal{R}$$ which is pairwise disjoint, and for which $$\bigcup_nA_n\in\mathcal{R}$$) and the countably subadditivity of $$\mu$$(i.e., condition (iv) of Theorem R).
• The labors of Carathéodory allows one to construct the Lebesgue (and more generally Lebesgue-Stieltjes) measure on the real line starting from the ring of intervals $$\mathcal{R}=\{(a,b]: -\infty and $$\mu((a,b]):=F(b)-F(a)$$ where $$F$$ is monotone-nondecreasing and right continuous ($$F(x)=x$$ yields Lebesgue's measure is the case discussed in Theorem 6.5 of thaformentioned textbook).

Proof of Theorem R Assume $$\mu$$ a premeasure on $$\mathcal{R}$$ (in the sense outlined by the OP). Parts (i) and (ii) hold trivially: (i) by definition of premeasure and (ii) by taking $$A_1=A$$, $$A_2=B$$, and $$A_n=\emptyset$$ for all $$n\geq 3$$.

For any sets $$A, B$$, $$A=(A\setminus B)\cup (A\cap B)$$. Thus, if $$A,B\in\mathcal{R}$$,$$A\setminus B$$ is the finite union of pairwise disjoint sets, say $$D_1,\ldots, D_k$$, in $$\mathcal{R}$$. If $$\mu(A)<\infty$$ or $$\mu(A\cap B)<\infty$$, it follows from part(ii), that $$\sum^k_{j=1}\mu(D_j)=\mu(A)-\mu(A\cap B)$$ which shows that the sums of the premeasures of the finite pairwise disjoint components of $$A\setminus B$$ does not depends of how the $$A\setminus B$$ is decomposed as a finite pairwise disjoint union of ell ents in $$\mathcal{R}$$. Thus, the quantity $$\bar{\mu}(A\setminus B):=\sum^k_{j=1}\mu(D_j)=\mu(A)-\mu(A\cap B)$$ is well defined whenever $$\mu(A)<\infty$$ or $$\mu(A\cap B)<\infty$$.

Another consequence of parts (i) and (ii) is that if $$A\in\mathbb{R}$$ and $$B\subset A$$ is the finite union of pairwise disjoint sets, say $$B_1,\ldots, B_k\in\mathcal{R}$$, then $$\sum^k_{j=1}\mu(B_k)\leq \mu(A)$$ Indeed, it can easily proved by induction in the $$k$$ that $$A\setminus \bigcup^k_{j=1}B_j$$ is the finite union of pairwise disjoint sets, say $$C_1,\ldots,C_m\in\mathcal{R}$$. Thus $$\{B_j,C_\ell:1\leq j\leq k,\,1\leq \ell\leq m\}$$ is a collection of pairwise disjoint sets in $$\mathcal{R}$$ and so, $$A=\Big(\bigcup^k_{j=1}B_j\Big)\cup\Big(\bigcup^m_{\ell=1}C_\ell\Big)$$ Hence $$\mu(A)=\sum^k_{j=1}\mu(B_j)+\sum^m_{\ell=1}\mu(C_\ell)\geq \sum^k_{j=1}\mu(B_j)$$

Part (iii) is the only one that requires a little work. Suppose $$B_n$$ is an increasing sequence in $$\mathcal{R}$$, i.e. $$B_n\subset B_{n+1}$$ for all $$n\in\mathbb{N}$$, such that $$B:=\bigcup_nB_n\in\mathcal{R}$$. Since $$\mu(B_{n-1})\leq \mu(B_n)$$, it is enough to assume that all $$\mu(B_n)<\infty$$.

Let $$A_1:=B_1$$, and $$A_n=B_n\setminus B_{n-1}$$. Clearly the collection $$\{A_n\}$$ is pairwise disjoint, and $$B=\bigcup_nA_n$$. Each $$A_n$$ is the finite union of disjoint elements, say $$C_{n1},\ldots,C_{nk_n}$$, of $$\mathcal{R}$$. Then the collection $$\{C_{n,j}:n\in\mathbb{N}, \,1\leq k_j\leq n\}$$ is a countable pairwise disjoint collection of sets in $$\mathcal{R}$$. Since $$A_n=\bigcup^{k_n}_{j=1}C_{n,j},\qquad B=\bigcup^\infty_{n=1}\big(C_{n1}\cup\ldots\cup C_{nk_n}\big)$$ we have that by part (ii) that $$\bar{\mu}(A_n)=\sum^{k_n}_{j=1}\mu(C_{nj})=\mu(B_n)-\mu(B_{n-1})$$, where $$B_0=\emptyset$$. Since $$\mu$$ is a premesure \begin{align} \mu(B)&=\sum^\infty_{n=1}\sum^{k_n}_{j=1}\mu(C_{nj})=\sum^\infty_{n=1}\bar{\mu}(A_n)\\ &=\mu(B_1)+\sum^\infty_{n=2}\mu(B_n)-\mu(B_{n-1})=\lim_n\mu(B_n) \end{align}

(iv) Follows similarly. It suffices to consider the case where $$\mu(B_n)<\infty$$ for all $$n$$. Let $$A_1=B_1$$ and $$A_n=B_n\setminus A_{n-1}$$. By induction each $$A_n$$ is be written as the finite union of sets, say $$D_{n1},\ldots, D_{nk_n}\in \mathcal{R}$$. Then $$A_n=B_n\setminus A_{n-1}=\bigcup^{k_n}_{j=1}D_{nj}\subset B_n,\qquad B=\bigcup^\infty_{n=1}\big(D_{n1}\cup\ldots\cup D_{nk_n}\big)$$ As $$\mu$$ is a premeasure and $$\{D_{nj}:n\in\mathbb{N},\,1\leq j\leq k_n\}$$ is a countable collection of pairwise disjoint sets in $$\mathcal{R}$$, we have that $$\mu(B)=\sum^\infty_{n=1}\Big(\sum^{k_n}_{j=1}\mu(D_{nj})\Big)\leq\sum^\infty_{n=1}\mu(B_n)$$

I leave to the OP the task to convince himself/herself- most like this is already the case- that when $$\mathcal{R}$$ is a ring, then Theorem 4.4 holds when $$\mu$$ is a premeasure on $$\mathcal{R}$$. Only sufficiency requires a proof, but this becomes easy as $$A\setminus B$$, and $$A\cup B$$, and $$A\cap B$$ belong to $$\mathcal{R}$$ whenever $$A,B\in\mathcal{R}$$.

Edit:

• In the first edition, the author does actually refer to (iii)' in his construction of Lebesgue measure on $$\mathbb{R}^n$$. He argues that (a) $$\lambda:\mathbb{R}\rightarrow\mathbb{R}$$, where $$\mathcal{R}=\{\prod^n_{j=1}[a_j,b_j): a_j, given as $$\lambda(\prod^n_{j=1}[a_j,b_j))=\prod^n_{j=1}(b_j-a_j)$$ satisfies condition $$(iii)'$$; (b) this in turn implies (iii); (c) and so $$\lambda$$ is a pre-measure by the converse of Theorem 4.4. That logic is not correct for as the OP pointed out, $$\mathcal{R}$$ is not a ring.

• In the second edition of the book (pages 46-50), the construction if the Lebesgue measure on $$\mathbb{R}^n$$ is rewritten and no reference to (iii)' is used. Conditions (i), (ii) along with countably additivity are derived in his presentation by topological arguments.

• Thanks for the answer but it seems to me that you didn't answer the question. My Question is: "Is Theorem 0.2 True? What is the proof of the implication from the right to the left of the Theorem0.2? And if that implication of the theorem0.2 is not true can you show me an example of a function $\mu$ on a set $X$ with the properties (i), (ii), (iii'') of the theorem0.2 but such that $\mu$ is not a premeasure?" You didn't tell me if Theorem0.2 is true and you didn't show me the proof of the implication that interests me ( Which is the one in which you have to prove that $\mu$ is a premeasure ) May 8 at 21:46
• Moreover even if your proof of Theorem R is really interesting, Your theorem R is basically the implication that i already proved of the theorem 0.2, with the exception that you also proved the property (iv) May 8 at 21:50
• I also don't understand why you left to me the task to verify that Theorem4.4 still holds when $\mu$ is a premeasure on a ring since I said in the question that i succeeded in proving this fact (look at my Theorem 0.1 and what i said before it) May 8 at 21:54
• @irbag: Theorem 0.2 (as stated in your OP) does not appear in the textbook you are reading; only the necessity version of it (Theorem R (i), (ii) and (iv) ) derived within the process proving Charathéodory's extension theorem is used. The author exploits (i), (ii) and (iv) to extend $\mu$ to a collection $\mathcal{R}_\cup$ which happens to be a ring and then all pieces fall into place. (to be continued) May 8 at 22:21
• May 8 at 22:26


text:
" /> -->

#### Sets, Relations and Functions Two Marks Questions

11th Standard

Reg.No. :
•
•
•
•
•
•

Maths

Time : 00:45:00 Hrs
Total Marks : 30
15 x 2 = 30
1. State whether the following sets are finite or infinite.
{x $\in$ N:x is an odd prime number}

2. State whether the following sets are finite or infinite.
{x $\in$ Z:x is even and less than 10}

3. Let A and B be two sets such that n(A)=3 and n(B)=2. If (x, 1) (y, 2) (z, 1) are in A$\times$B, find A and B, where x, y, z are distinct elements.

4. Let X = {a, b, c, d}, and R = {(a, a) (b, b) (a, c)}. Write down the minimum number of ordered pairs to be included to R to make it
Reflexive

5. If U={x:1≤x≤10, x∈N}, A={1,3,5,7,9} and B={2,3,5,9,10} then find A'UB'.

6. If A⊂B then find A⋂B and A\B (using venn diagram)

7. On the set of natural number let R be the relation defined by aRb if a + b $\le$ 6. Write down the relation by listing all the pairs. Check whether it is reflexive

8. On the set of natural number let R be the relation defined by aRb if a + b $\le$ 6. Write down the relation by listing all the pairs. Check whether it is symmetric

9. Find the number of subsets of A if A = $\{x :x = 4n + 1, 2 \le n \le 5, n \in N\}.$

10. If f and g are two functions from R to R defined by f (x) = 4x - 3, g(x) = x2 + 1, find fog and gof.

11. On a set of natural numbers let R be the relation defined by aRb if a + 2b = 15. Write down the relation by listing all the pairs. Check whether it is reflexive, symmetric, transitive, equivalence.

12. If  $f(x)=\frac { x-1 }{ x+1 }$, then show that $f\left( \frac { 1 }{ x } \right) =-f(x)$

13. If  f(x)=$\frac { x-1 }{ x+1 }$, then show that, f$\left( \frac { -1 }{ x } \right) =\frac { -1 }{ f(x) }$.

14. If A = { 0, 1, 2, 3, 4, 5, 6, 7 } is a set. Then,

15. Try to write the following intervals in symbolic form:
(i) $\{x:x\in R,-2\le x \le 0 \},$
(ii) $\{ x:x\in R, 0<x< 8 \},$
(iii) $\{ x:x \in R, -8\le -2 \}$
(iv) $\{x:x\in R, -5\le x \le 9 \}$


text:
It is currently 20 Feb 2018, 17:41

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# At a constant speed of 72 kilometers per hour, a vehicle travels

Author Message
TAGS:

### Hide Tags

Intern
Joined: 16 Oct 2017
Posts: 24
At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

09 Feb 2018, 19:36
00:00

Difficulty:

15% (low)

Question Stats:

81% (00:37) correct 19% (00:50) wrong based on 32 sessions

### HideShow timer Statistics

At a constant speed of 72 kilometers per hour, a vehicle travels how many kilometers per second?

A) 0.02
B) 0.2
C) 0.6
D) 1.2
E) 6.0
[Reveal] Spoiler: OA
Intern
Joined: 31 Dec 2017
Posts: 18
Concentration: Finance
Re: At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

09 Feb 2018, 20:03
OCDianaOC wrote:
At a constant speed of 72 kilometers per hour, a vehicle travels how many kilometers per second?

A) 0.02
B) 0.2
C) 0.6
D) 1.2
E) 6.0

72 kilometers in 60 mins, there are 60*60 = 3600 secs in 60 mins, so distance travelled in one second = 72/3600 = 2/100 = 0.02. (A).
Math Expert
Joined: 02 Aug 2009
Posts: 5658
Re: At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

09 Feb 2018, 20:43
OCDianaOC wrote:
At a constant speed of 72 kilometers per hour, a vehicle travels how many kilometers per second?

A) 0.02
B) 0.2
C) 0.6
D) 1.2
E) 6.0

The number is in km per hour but answer asked is in km per second...
So 72 km per hour = $$\frac{72}{60*60}=\frac{72}{36*100}=\frac{2}{100}=0.02$$
A
_________________

Absolute modulus :http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html

BANGALORE/-

Manager
Joined: 31 May 2017
Posts: 67
Re: At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

09 Feb 2018, 22:51
72 kilometers per hour translates to 72 kilometers in 3600 seconds.

Distance traveled per second = 72/3600 = 0.02

Ans: A
_________________
BSchool Forum Moderator
Joined: 07 Jan 2016
Posts: 466
Location: India
GMAT 1: 710 Q49 V36
Re: At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

09 Feb 2018, 23:21
72 kmph

in km/sec

convert hours into seconds
1 hr = 3600 seconds

72/3600

2/100

0.02
Intern
Joined: 31 Jan 2018
Posts: 16
Re: At a constant speed of 72 kilometers per hour, a vehicle travels [#permalink]

### Show Tags

10 Feb 2018, 05:15
72 kilometers in 60 mins, there are 60*60 = 3600 secs in 60 mins, so distance travelled in one second = 72/3600 = 2/100 = 0.02.
Re: At a constant speed of 72 kilometers per hour, a vehicle travels   [#permalink] 10 Feb 2018, 05:15
Display posts from previous: Sort by