rattle – Page 5 – nullteilerfrei

Why someone thought that sudoku might not be boring, while actually you should learn how to properly implement backtracking

rattle code, technology 2014-07-03

It causes me unspeakable agony to see that my post about why sudoku is boring is one of the most frequented posts in this blog, mostly because most of my readers clearly disagree with the title. I recently received an email titled "why sudoku is not all that boring" by an old friend, and he taunted me that the sudoku

S = [
  0, 0, 0, 0, 6, 0, 0, 8, 0,
  0, 2, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 7, 0, 0, 0, 0, 1, 0, 2,
  5, 0, 0, 0, 3, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 4, 0, 0,
  0, 0, 4, 2, 0, 1, 0, 0, 0,
  3, 0, 0, 7, 0, 0, 6, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 5, 0 ]

would take my 5-minute hack of a backtracking algorithm

real    51m3.656s
user    50m32.260s
sys     0m2.084s

to solve. So, it seems like some sudokus are really hard, even for a computer, right? Wrong wrong wrong wrong wrong. Read how to implement backtracking properly.

Offline Maps

rattle technology 2014-05-24

It used to be a problem to get good route planning on your smartphone when you are outside the country, because the roaming fees could plunge any McKinsey employee into bankrupcy when using Google Maps, which is only able to cache small map sections and basically has no way of telling you what is cached and what isn't. Rejoice! The OSMAND project provides an open maps and route planning solution which allows you to download all kinds of maps for offline use. I personally like the Android App even better than Google Maps: It's clearly for power users, there is much more to configure and you have more control. There is always an obvious argument for choosing another option over the kraken, but the option to download maps for offline use has to be the main reason why this is awesome. The entire Open Street Map project (see also the German version) seems to be a cool project which is worth contributing to, even if it's just pointing out a house number here and there.

Migrating from Opera 12 to Firefox

rattle technology

Opera was updated. They messed up. Let's not talk about this any more. Let's talk about how to make Firefox your new Opera 12. To get the elephant out of the room right away: Yes, you guessed right, I did not switch to Chrome because I am scared of Google harvesting all my data and browsing habits. So that leaves only Firefox, and I think that they did good with the recent releases. We probably can not get back everything we miss from Opera 12 times, but some of it is possible, and even better in Firefox. First of all, Firefox has bookmarks and you can import them from an HTML export of your old bookmarks. For everything else, continue reading. If you are still missing a feature, feel free to post it with or without solution - in the latter case, I will try and solve it myself. (more…)

Irreducible Highest Weight Vectors

rattle mathematics 2014-05-23

Let $G$ be an affine, connected, reductive group and $X$ a $G$-module. Choose a maximal torus $T\subseteq G$, a Borel $B\subseteq G$ containing $T$ and let $U$ be the unipotent radical of $B$. Denote by the character group of $T$. Let $\Lambda\subseteq\mathbb{X}$ be the set of dominant weights of $G$ with respect to these choices. We can decompose the graded coordinate ring $\mathbb{C}[X]=\bigoplus_{\lambda\in\Lambda} V_{(\lambda)}$ into its isotypic components $V_{(\lambda)}$ of weight $\lambda$. Let \[ \Lambda_X=\{ \lambda\in\Lambda \mid V_{(\lambda)}\ne\{0\}\} \] be the set of weights that occur in $\mathbb{C}[X]$. Let $V_{(\lambda)}\cong V_\lambda^{\oplus n_\lambda}$, where $V_\lambda$ is the irreducible module of highest weight $\lambda$. Each $V_\lambda$ has a highest weight vector which is unique up to scaling - let $f_{\lambda 1}, \ldots, f_{\lambda n_\lambda}\in V_{(\lambda)}$ be linearly independent highest weight vectors. Claim. *For each $1\le k\le n_\lambda$, if the function $f:=f_{\lambda k}\in\mathbb{C}[X]$ is reducible, then there exist weights $\lambda_1,\ldots,\lambda_r\in\Lambda_X$ such that $\lambda$ is an $\mathbb N$-linear combination of the $\lambda_i$.* Indeed, about a year ago this statement was completely unclear to me. However, it's actually not that hard to see and I felt like sharing my proof. (more…)

A determinant for reductive groups

rattle mathematics 2014-05-17

For the group $G=\mathrm{GL}_n(\mathbb{K})$ of invertible matrices over any field, there is the well-known determinant character $\det:G\to\mathbb{K}^\times$ which, well, maps any matrix to its determinant. It has the property that \[ [G,G]=\mathrm{SL}_n(\mathbb{K})=\{ g\in G \mid \det(g)=1 \}, \] where $[G,G]$ denotes the derived subgroup of $G$. In more geometric terms, $[G,G]$ is the vanishing of the regular function $\det-1$ on $G$. Because I find it rather cute, I will show that you can find a similar function for all linear, reductive groups. (more…)

Das Master Theorem

rattle mathematics 2014-05-06

Ich habe letzte Woche versucht, für einige Studenten das Master Theorem zu beweisen. Das ist geringfügig daneben gegangen, deswegen habe ich eine korrigierte Version des Beweises erstellt. Ich frage mich nun aber schon, wie allgemein man das eigentlich machen sollte. Grundsätzlich könnte man sich für eine Laufzeitfunktion $T:\mathbb N\to\mathbb N$ ja Rekurrenzgleichungen der Form $T = \alpha \circ T \circ \beta$ ansehen, wobei in meinem Fall $\beta(n)=n/b$ und $\alpha(n)=a\cdot n + f(n)$ ist. Ich habe leider keine Zeit, mir dazu mehr Gedanken zu machen.

Make VIM work in Cygwin

rattle technology 2014-05-01

Well. In case you have not stumbled across the corresponding StackOverflow post, and if you have always wondered why vim does not work properly in cygwin, just

[rattle@ALICE:~]$ cat .vimrc
set nocompatible
set backspace=indent,eol,start

and your worries will be over.

Keep Cygwin Applications from setting NTFS security descriptors

rattle productivity, technology 2014-04-07

If you run cygwin applications such as [the rsync-backup script](/2014/01/31/incremental-backups-with-rsync-in-windows/), you will sometimes run into trouble with odd NTFS permissions being set by the cygwin application. My tip is to avoid this by making cygwin not set *any* permissions at all. If a cygwin application then creates a file, for instance, this file will only inherit its security settings from the folder it is contained in. This way, you can set access control on the root directory and all the files created by rsync inside that folder will inherit these permissions. How to do it? Open your cygwin shell and edit /etc/fstab which should contain only one non-comment line:

none /cygdrive cygdrive binary,posix=0,user 0 0

Now insert the noacl attribute, see [the cygwin manual](http://www.cygwin.com/cygwin-ug-net/using.html#mount-table):

none /cygdrive cygdrive binary,noacl,posix=0,user 0 0

And the next time you run rsync-backup, it will *not* set all kinds of awkward permissions on your files which make them unreadable on a freshly installed computer. Just saying.

Complements of affine schemes

rattle mathematics 2014-04-04

I asked a question on mathoverflow, and while researching I stumbled upon a theorem which I did not know before. I consider it quite powerful and the proof is short and sweet, I copied it from this expository paper by Bryden Cais: Theorem. Let $X$ be a normal, separated, Noetherian scheme and $U\subseteq X$ a nonempty affine open subset. Then, $X\setminus U$ is pure of codimension one. Proof. We need to show that for each generic point $y\in Y=X\setminus U$, the local ring $\mathcal{O}_{X,y}$ has dimension one. Let $y$ be the generic point of a component of $Y$. Denote by $\mathfrak{m}$ the maximal ideal of the local ring $A:=\mathcal{O}_{X,y}$. Let $S:=\mathrm{Spec}(A)$. The inclusion morphism $f:S\to X$ is affine because $X$ is separated (Lemma 1). Thus, $V:=f^{-1}(U)=S\setminus\{ \mathfrak{m} \}$ is an affine, open subscheme of $S$. The morphism on global sections $A=\mathcal{O}_S(S)\to\mathcal{O}_{V}(V)$, corresponding to the inclusion $V\to S$, is therefore injective. It can not be surjective because $V\ne S$. Pick some $a\in\mathcal{O}_{V}(V)\setminus A$. If we now had $\dim(A)>1$, then the prime ideals of height one $\mathfrak{p}\subseteq A$ would satisfy $\mathfrak{p}\ne\mathfrak{m}$, i.e. they would correspond to points contained in $V$. Consequently, we would have $a\in \mathcal{O}_{V,\mathfrak{p}} = A_{\mathfrak{p}}$. Because $A$ is a normal Noetherian domain, it is the intersection of all localizations at prime ideals of height one - this is Corollary 11.4 in Eisenbud's book. This yields the contradition that $a\in A$. Lemma 1. If $f:X\to Y$ is a morphism of schemes with $Y$ separated and $X$ affine, then $f$ is an affine morphism. Proof. This is exercise 3.3.6 in Qing Liu's book. Let $V\subseteq Y$ be an open affine subset. Proposition 3.9(f) in the same book tells you that there is a closed immersion $f^{-1}(V)\cong X\times_Y V\to X\times V$, so $f^{-1}(V)$ is isomorphic to a closed subscheme of an affine scheme, hence affine.

The Onebag

rattle productivity 2014-03-11

I have been commuting between cities quite a lot for quite a while now, and I have given the issue of travel practicability quite a lot of thought. I was urged to share these thoughts, and so I obey. Let's start with the motivation: The worst thing that can happen to me on a trip is to be missing that one essential item, say a charging cable. This happened to me a lot because I usually do not have my charging cable with me at all times. It's at home, where I charge my phone/laptop. The solution for this kind of problem is redundancy. I present the concept of the onebag: It is the one bag which always contains everything you really need. That essential assortment of items should be in your onebag at all times. Mind you, though: Your onebag contains the items you'll need on every trip, it does not contain every item you will need on a trip. Its purpose is to never leave you pondering if you forgot something important. My onebag is broken down into three levels: * Level 1: I have a USB stick attached to my key ring which contains all my most precious data. Together with my wallet and my phone, this is level 1. This stuff is with me at all times. * Level 2: I use an organizer casket for all my electronic devices and cables that I usually need for work, together with my laptop this is level 2. I take these items to work every day, but I do not take them with me when I go out to buy groceries. * Level 3: A red backpack. It contains duplicate copies of all my charging cables in this cable organizer, hygiene products ((I have been thinking about putting a towel in there, but I never really need one. Hotels and friends give you towels, and one of those is usually where I stay.)), one change of underwear and binbags. Together with levels 1 and 2, this is my onebag. This is just an example of course. The point is to minimize thinking about "what to pack". If I need to go to another city for 3 days, I grab level 2 and stuff it into the bag, take 3 shirts and 3 changes of underwear and I am essentially done. If you did it right, about 98% of your travel preparations should be as simple as packing the clothes you need for the trip into your onebag. For some trips, you might need an additional bag for more clothes or you might need to pack some items which are very specific to the trip you are about to take: But your essential gear is already in the bag.

New design

rattle remark 2014-03-02

I decided to switch to the new design made by Roman for us, even though he protests that it is not finished. After a long sequence of emails, I managed to pester him into letting me fix the remaining technical wordpress issues with several dirty hacks myself, and there we are. This layout is responsive and will work properly on smartphones. Just two months ago, I could not have cared less about such things, but now I have a smartphone myself.

Do not use the Amazon App Store

rattle remark 2014-02-06

As some of you might know, I got my first mobile device now and started playing around with it. Today, I need to rant, because I lost 79 cents. When you buy an app on the amazon app store, you can no longer use it after you uninstall the amazon app store. Other android users also hate the amazon app store because it is an obnoxious app which is mean and does not let you use apps which you paid for with money after you get rid of the data-leaking abomination it is. Do not use it. I simply bought ownCloud on the humble, trustworthy google play store again. I have no time to deal with amazon over those 79 cents. But I have time to write this scornful post.

TeXStudio: Endlich keine AutoCompletion mehr.

rattle latex, technology 2014-02-02

Ich habe endlich herausgefunden, wie man auch die letzten merkwürdigen Autovervollständigungen von TexStudio eliminert. Das Problem ensteht vor allem mit deutschen Tastaturen, da man häufig Ctrl+Alt noch gedrückt hat, wenn man die Leertaste betätigt, etwa nachdem man eine schließende, geschweifte Klammer (Ctrl+Alt+0 liefert }) eingegeben hat. Dies hat in der TexStudio Standardkonfiguration zur Folge, dass ein \begin{ im Text eingefügt wird. Wie schaltet man das aus? So: * TexStudio konfigurieren * Tastenkürzel * Menüs * Idefix * Vervollständige * Den \begin{ Vervollständigungs-Hotkey löschen Es könnte noch andere Ctrl+Alt-Makros dieser Art geben, die man löschen sollte. Ich werde diesen Post updaten, wenn mir weitere unterkommen.