A method that defines the superset of Mary permutation frequency-shift keying (SPFSK) alphabets as the symbol space is investigated as a possible robust data link for the underwater acoustic (UWA) channel. The alphabet is equivalent to on-off keying for M=1. Polar coding and time/frequency guards are used for redundancy. The bit error probability of an SPFSK symbol is evaluated to construct the Polar code; it is found to be uniform across bit positions in the label by using natural labeling due to a symmetric fractal behavior in the pairwise symbol error probability, and the heuristic code construction method is directly applicable. A Ricean noncoherent data model is used, and a reduced complexity algorithm for calculating binary log-likelihoods is provided. The method is simulated in an additive white Gaussian noise channel to find a good Polar code construction and evaluate different alphabet parameterizations; the results show that the receiver statistics improve with the alphabet size. SPFSK is further evaluated in the public Watermark benchmark, using both genie- and pilot-assisted parameter tracking, as well as perfect and nonperfect synchronization. Results from the Watermark replay channels NOF1, NCS1, and BCH1 show that ≲ 1% frame error rate is attained at 16≤ b/N0 ≤ 23 dB depending on the channel, using ∼ 0.2 bit/s/Hz spectral efficiency, indicating its potential as a robust data link. Performance in the UWA channel increases substantially by using many tones, and the statistical model must be sufficiently accurate to leverage the processing gain of an SPFSK alphabet with higher dimensionality.